donné deux nombres a, b tels que 1 <= a, b <= 10000000000 (10 ^ 10). Mon problème est de vérifier si les chiffres d'entre eux sont permutés les uns des autres ou non. Quel est le moyen le plus rapide de le faire? J'avais pensé à utiliser le hachage mais incapable de trouver une fonction de hachage appropriée. Toute suggestion?
pour E.g - 123 est une permutation valide de 312
9 Réponses :
est-ce que ce devoir est de devoir?
Calculer le nombre d'apparences de chaque chiffre et les comparer, s'ils sont les mêmes, un nombre peut être converti en une autre utilisation de la permutation.
Arttyom: Cela ressemble plus à un problème d'apéritif d'un concours de programmation comme ICPC.
Cela se voit également souvent sur les questions du projet Euler, par exemple. # 49.
Si vous voulez dire les caractères des chiffres (tels que 1927 et 9721), il existe (au moins) quelques approches.
Si vous avez été autorisé à trier, une approche est simplement Cependant, étant donné votre désir de pas em> trier les chiffres, une autre alternative Il est de configurer une matrice de dix éléments, avec tous les éléments initialement définis sur zéro, puis traitez chaque chiffre dans le premier nombre, incrémentant l'élément pertinent. p> puis faites la même chose avec le deuxième nombre mais en décrément. P> Si, à la fin, il est toujours tous des zéros, les chiffres étaient une permutation l'une de l'autre. p> Ceci est efficace en ce que c'est un in c, le programme complet ci-dessous illustre comment cela peut être effectué: P> Sprintf sur deux tampons, triez les caractères dans les tampons, puis voir si les chaînes sont égales. p> O (n) Code> Algorithme où n code> est le nombre de chiffres dans les deux nombres. Le pseudo-code pour une telle bête serait quelque chose comme: p> int main (int c, char *v[]) {
long v1, v2;
if (c != 3) {
printf ("Usage: %s <number1> <number2>\n", v[0]);
return 1;
}
v1 = atol (v[1]);
v2 = atol (v[2]);
if (hasSameDigits (v1, v2)) {
printf ("%d and %d are permutations\n", v1, v2);
} else {
printf ("%d and %d are not permutations\n", v1, v2);
}
return 0;
}
Est-il possible de le faire sans faire de type de tri?
Pouvez-vous également suggérer quelque chose sur la ligne de hachage aussi?
Je dirais que cela ressemble déjà à la hachage. Chaque chiffre est stocké dans un godet séparé en fonction de sa valeur de hachage (à l'aide d'une fonction de hachage triviale).
@Ravi, il n'y a pas besoin d'un hasch. Comme indiqué déjà par Jalf, c'est déjà une fonction de hachage simple mais parfaite (de TRES), étant donné le nombre limité de godets requis. Toute tentative d'essai et d'ajouter plus de code compliqué va plus que probablement la ralentissement, autres que des optimisations évidentes bien sûr (telles que si (Num1 == num2) renvoie vrai; au début).
@paxdiablo, hé, tu as dupé Ravi en faisant de la sorte de radix!
@Ravi: C'est à la fois le tri et le hachage. Lorsque vous indexez un tableau par une fonction d'un sous-ensemble des bits d'une clé, c'est hachage. Lorsque la fonction préserve la commande, c'est une forme d'index ou de tri radix. Le moyen le plus rapide de trier un ensemble d'entiers O (n) est de les utiliser comme indices dans une table.
@paxdiablo "C'est efficace en ce que c'est un algorithme O (n) où n est le nombre de chiffres dans les deux nombres." Ou, pour en regarder un autre moyen, c'est O (log n) sur les chiffres eux-mêmes, non? Parce que le nombre de chiffres en n est (plancher (log10 (n)) + 1) ... :)
Créer un tableau: in si les deux tableaux sont égaux, les nombres sont des permutations. < p> Ceci est un algorithme O (n), ainsi asymptotiquement, c'est le plus efficace qu'il va obtenir (vous ne pouvez pas résoudre ce problème sans examiner tous les chiffres au moins une fois. Vous pouvez Renvoie immédiatement False si les chiffres ont des longueurs différentes, supposons donc que les deux sont de longueur n. Il prendra des opérations 2n pour remplir la matrice, puis 10 comparaisons pour lire le tableau. 2n + 10 est O (n). / p> digitoccruances [x] [n] stocke le nombre de fois que le chiffre n apparaît Dans le nombre x . Donc, si vous compariez 8675309 à 9568733, la matrice finirait par ressembler à:
Ici n dans le O (n) est le nombre de chiffres. Beaucoup de gens peuvent appeler ce O (journal x) où x est le numéro. Il n'y a aucun moyen de le faire en moins de O (journal x) heure, mais dans la pratique si x correspond à un type de variable entier, O (journal x ) est constant. Quoi qu'il en soit, si n est grand (parler de chaînes entière non des variables C Simple C) Il n'y a certainement aucun algorithme mieux que O (n) puisque vous devez examiner chaque chiffre au moins une fois que...
@R ..: De plus, tout o (f (n)) devient O (1) si n est corrigé.
R, je crois que ces gens seraient trompés. La notation Big-O est censée être une fonction du jeu de données taille ( n ), pas le jeu de données valeur ( x ). Je pense que vous avez raison que o (n) est aussi bon que vous allez faire, à court de temps de négociation pour l'espace :-)
@paxdiablo Vous êtes correct dans ce "code> n dans big-o est la taille d'entrée et la saisie est la saisie des chiffres, pas le numéro lui-même. Cependant, il existe un précédent pour classer ces types de problèmes basés sur la valeur d'entrée x à la place. Ceci est normalement fait lorsqu'il est en termes de n un algorithme est super polynomial, mais en termes de x il est polynomial. Ces algorithmes, souvent pour les problèmes complets NP, sont dites couragés dans "Temps pseudo-polynomial" ( en.wikipedia.org/wiki/pseudo-polynomial_time ). Donc, je suppose que par analogie, nous pourrions dire que cet algorithme fonctionne dans une "période pseudo-logarithmique".
@Tyler: Bien que le titre du papier AKS est "Primes est en P", pas "Les nombres premiers sont pseudo-polynomiaux-logarithmiques" ;-) Je préférerais voir / dire "O (quelque chose impliquant x), où x est ... »que de compter sur tout le monde en utilisant le même jargon, sauf dans un contexte académique.
a et b sont des anagrammes s'ils ont le même nombre de chiffres. Donc, fondamentalement, le moyen le plus rapide semble être en comptant les chiffres de A et B:
int c[10]={0,0,0,0,0,0,0,0,0,0}
while (a) { c[a%10]++; a/=10; }
while (b) { c[b%10]--; b/=10; }
int res=1;
for (int i=0;i<10;i++) res &= c[i]==0;
printf(res?"yes":"no");
C'est pourquoi ils disent que C a tout le pouvoir de la langue d'assemblage avec toute la lisibilité de, eh bien, langage de montage :-)
+1 pour une meilleure réponse. Compter les chiffres est optimal. Le tri est lent.
Au fait, int c [10] = {0}; est tout aussi bon pour l'initialisation de la matrice. Et vous pourriez memcmpp avec un tableau Constant-0 pour vérifier les résultats avec moins de code. :-)
@R: ou utiliser wind_if - probablement plus de code que le memcmp avec 0-tableau, mais plus Leet.
@R: Compter les chiffres est un type de tri.
@jamesdlin: compter les chiffres est (la partie principale de) une méthode de tri. Si vous n'assumez pas réellement / sortie les chiffres triés, cependant, alors (1), vous ne les avez pas triés, et (2) vous avez enregistré un peu de temps. Si ce délai est mesurable est un autre problème, mais le fait est que ce code fait pas trier les chiffres de a et b . Il dispose d'un état intermédiaire dans lequel il serait facile de produire les chiffres triés de A .
@paxdiablo C'est aussi pourquoi c est supérieur à une autre langue dans ce scénario - problèmes amusants et sans importance :)
Eh bien, si vous pouvez construire une table de 80 Go, vous pouvez toujours faire:
int64 table[10000000000] = {0, blah blah..., 9999999999};
if (table[a] == table[b]) ...
Je pense qu'il y a peu de classes d'équivalence suffisantes que vous n'avez pas besoin de 64 bits. Je devrais vous donner -1 pour écrire int64 (une étrangeté non standard ..?!) Au lieu de intz_t (iso c) ...
@R ..: Gosh, désolé d'être non standard (encore moins étrange). Billg Interdit! Quoi qu'il en soit, vous avez raison de moins de classes d'équivalence. En fait, je viens de faire un compte de force brute - 92378.
{édité pour ajouter du test supplémentaire)
En supposant que vous êtes dans le domaine des chiffres, que diriez-vous de
Nan. Notez que '0' ^ '3' == '1' ^ '2' par exemple.
Bonne idée, cependant. Si les sommes du chiffre sont différentes, ils ne sont pas équivalents.
Si ce que j'ai compris de votre question correctement, une permutation est une combinaison des éléments qui ne se répètent pas. Donc, si 123 est une permutation valide de 312, alors et ainsi de suite. P> Basé sur cette hypothèse indique que vous avez deux entiers 123456789 et 129837456. (Pour la simplicité, je suppose également que les deux chiffres ont une longueur égale). Si vous avez compris le point, vous pourrez peut-être vérifier également des permutations et une combinaison différentes. P> Pour que tout ce que vous avez à faire est d'obtenir les entiers des unités hors du nombre donné, par exemple: 1, 2, 9, 8, 3, 7, 4, 5, 6
Vos solutions sont l'une des solutions possibles mais non efficaces telles que les autres solutions publiées dans ce problème.
Eh bien, ma solution n'était pas en réalité une solution, mais plutôt un indice qui pointera la solution ou comment nous pouvons y parvenir. Comme je suis un défenseur d'apprendre par votre propre pratique et par d'autres expériences. Donc, si je fournis toute la solution, je l'obligerai à ne pas utiliser son esprit du tout. Et oui définitivement, il peut y avoir un certain nombre d'optimisation pour le calcul. Mais les optimisations ne viennent qu'après que nous savons quoi faire.
J'ai trouvé cette solution assez efficace sur RosseCode.org . J'espère que vous voudrez que vous me pardonnerez de l'écrire à Java (je ne suis pas à l'aise avec c) mais la syntaxe doit être plus ou moins la même.
Le code vérifie d'abord pour voir si les chiffres ont le même nombre de chiffres. , résume ensuite les chiffres par le morceau les déplacent dans un total. Sauf que la distance de déplacement est multipliée par un facteur 6. Cela rend impossible pour des chiffres plus petits pour composer la même valeur qu'un chiffre plus gros. Par exemple, un "9" nécessiterait 64 fois "8" pour correspondre à sa valeur, ce qui n'est évidemment pas possible. P>
Ce code assume une entrée non négative. P>
boolean haveSameDigits(long n1, long n2) {
long nn1 = n1, nn2 = n2;
while (nn1 > 0 && nn2 > 0) {
nn1 /= 10;
nn2 /= 10;
}
if (nn2 != nn1) // not the same length
return false;
long total1 = 0, total2 = 0;
while (n1 != 0) {
total1 += 1L << ((n1 % 10) * 6);
total2 += 1L << ((n2 % 10) * 6);
n1 /= 10;
n2 /= 10;
}
return total1 == total2;
}
Je ne sais pas pourquoi vous ne voulez pas trier, à moins que c'était une condition de votre devoir. Pour quiconque trébuchant sur cette question à la recherche de Cette solution fonctionne légèrement Plus rapidement en python, s'appuyant, bien sûr, sur les chiffres testés pour être des entiers relativement faibles. Cela fonctionne assez bien pour le projet Euler Problème 52.
La question pose des questions sur C, pas python. En outre, un trier de hachage / radiix comme indiqué dans les autres réponses est plus rapide qu'un tri standard.
Comment un numéro peut-il être une permutation d'une autre? Parlons-nous de la chaîne de chiffres dans la base-10? Les chiffres 1-4-1 ne sont pas identiques au nombre 141.
Vous pouvez y penser aussi bien.
C'est essentiellement un chèque d'anagramme.