donné deux tableaux, comment vérifiez-vous si l'une est une permutation cyclique de l'autre?
Par exemple, étant donné Remarque: les tableaux peuvent avoir des éléments en double. a = [1, 2, 3, 1, 5] , b = [3, 1, 5, 1, 2] , et c = [2, 1, 3, 1, 5] Nous avons ce A et B sont des permutations cycliques mais c n'est pas une permutation cyclique de non plus.
4 Réponses :
Le truc standard ici est de concaténer l'un des tableaux avec lui-même, puis essayez de trouver le 2e tableau dans le tableau concaténé.
Par exemple, "A" concaténé avec lui-même est:
[1, 2, 3, 1, 5, 1, 2, 3, 1, 5]
Puisque vous voyez "B" dans ce tableau à partir du 3ème élément, puis a et b sont des permutations cycliques.
Je suppose que vous êtes présupposant les matrices sont de longueurs égales. Malgré cela, pourquoi n'est-il pas possible pour qu'il y a de faux positifs?
Oui. Si les tableaux ne sont pas de longueurs égaux, ils ne sont tridiment pas les permutations les unes des autres.
Si l'algorithme dit que c'est une permutation, ce sera par la construction. Si vous trouvez 'B' dans 'A' + 'A' à la position AI, alors si vous déplacez «A» par i par i pour que l'AI est le premier élément de 'A' Le wrap autour sera exactement la partie au 2e 'A' de la matrice concaténée que vous avez assortie.
C'est la preuve. L'algorithme vous dit exactement combien de déplacer «A» pour obtenir 'B »s'ils sont des permutations cycliques les unes des autres.
Si A et B sont des permutations cycliques l'une de l'autre, une volonté sera trouvée dans la liste doublée BB (de même que B dans AA).
Le moyen efficace de gérer de grandes quantités de données, consiste à transformer chacun d'entre eux en une forme "canonique" puis comparable à voir d'elles-mêmes. Pour ce problème, vous pouvez choisir comme forme canonique de toutes les permutations tournantes dont celle qui "trie le plus petit".
de sorte que la forme canonique pour 'a' et 'b' est [1, 2, 3, 1, 5] qui sont égales de sorte qu'ils sont des permutations acycliques.
La forme canonique pour 'C' est [1, 3, 1, 5, 2] qui est différente.
J'aime cet algorithme. C'est intuitif pourquoi ça marche. Pouvez-vous expliquer comment trouver la forme canonique lorsqu'il existe des éléments dupliqués (par exemple, le 1 dans a et b )?
Considérez les entrées comme des lettres et des permutations comme des mots. Le "mot" 12315 trie avant 15123, c'est donc le plus petit, c'est-à-dire canonique.
Je vois. Donc, la recherche de la représentation canonique prend O (n ^ 2) des comparaisons d'élément-sage où n est la longueur de la matrice? C'est-à-dire: boucle via tous les rotations possibles Conservez le minimum actuel, et pour chaque rotation, effectuez des comparaisons O (n) pour déterminer s'il faut mettre à jour le minimum. Peut-être qu'il y a une meilleure façon ..
@DSG Considérez le nombre de comparaisons si vous avez des tableaux à comparer, comme dans «de grandes quantités de données».
Au cas où, ce n'est toujours pas assez clair pour vous. Avoir une forme canonique signifie que vous pouvez hacher les valeurs pour accélérer les comparaisons.
Aimer! Je suis venu avec exactement cette représentation pour mon problème.
Voici une approche adhoc simple pour rechercher des permutations cycliques avec O (n) complexité de temps.
a = [1, 2, 3, 1, 5], B = [3, 1, 5, 1, 2] p>
Rechercher l'index de B [0] dans un [], disons index est 'X'..En début naviguer dans les deux array. a [] commence d'index 'x' et b [] commence à partir de '0'. De sorte que tous les deux doivent avoir les mêmes valeurs. Si Pas, ils ne sont pas cycliques. Voici le code d'exemple. P>
public class CyclicPermutation {
static char[] arr = { 'A', 'B', 'C', 'D' };
static char[] brr = { 'C', 'D', 'K', 'B' };
boolean dec = false;
public static void main(String[] args) {
boolean avail = true;
int val = getFirstElementIndex(brr[0]);
if(val ==Integer.MIN_VALUE){
avail = false;
return;
}
for (int i = val, j = 0; j <= brr.length-1; ) {
if (i > arr.length-1) {
i = 0;
}
if (arr[i] == brr[j]) {
i++;
j++;
} else {
avail = false;
System.out.println(avail);
return;
}
}
System.out.println(avail);
}
public static int getFirstElementIndex(char c) {
for (int i = 0; i <= arr.length; i++) {
if (arr[i] == c) {
return i;
}
}
return Integer.MIN_VALUE;
}
}
Cela ne fonctionnera pas, car le même personnage peut apparaître plusieurs fois dans un tableau
duplicaté possible de Question d'entretien: vérifiez si Une chaîne est une rotation d'une autre chaîne.
@Aryabhatta - Oui, c'est un duplicata. Merci d'avoir fait remarquer cela.