Inspiré par cette question et en particulier par le dernier paragraphe de la réponse de Ou, j'ai la question suivante: Connaissez-vous des applications de la théorie de la représentation du groupe symétrique dans TCS? Le groupe symétrique est le groupe de toutes les permutations de avec une...
Il y avait deux questions posées récemment sur cs.se qui étaient liées ou avaient un cas spécial équivalent à la question suivante: Supposons que vous ayez une séquence de n nombres tels que ∑ n i = 1 a i = n ( n + 1 ) . Décomposer en la somme de deux permutations, π et σ , de 1 … n , de sorte que...
À ma grande surprise, je n'ai pas pu trouver de documents à ce sujet - probablement recherché les mauvais mots clés. Donc, nous avons un tableau de tout, et une fonction sur ses indices; f est une permutation.ffffff Comment réorganiser le tableau selon avec une mémoire et une exécution aussi...
Quelle est la complexité de décider si un circuit avec bits d'entrée et bits de sortie calcule une permutation de ? en d'autres termes, si chaque chaîne de bits dans est une sortie du circuit pour une entrée? Cela ressemble à un problème qui a été étudié, mais je ne trouve aucune référence. nn{0,1...
Je voudrais poser une question sur un cas particulier de la question « Décider si un circuit NC 0 donné calcule une permutation » par QiCheng qui est resté sans réponse. Un circuit booléen est appelé circuit NC 0 k si chaque porte de sortie dépend syntaxiquement d'au plus k portes d'entrée. (Nous...
Pour tout , je dis qu'une séquence s d'entiers dans { 1 , … , n } est n -complète si, pour chaque permutation p de , écrite comme une séquence de paires entiers distincts , la séquence p est une sous-séquence de s , c'est-à-dire qu'il existe 1 ≤ i 1 < i 2 < ⋯ < i n ≤ | s |n>0n>0n >...
Shor a déclaré, dans son commentaire à la réponse d'un orignal anonyme à cette question Pouvez-vous identifier la somme de deux permutations en temps polynomial? , qu'il est complet d'identifier la différence de deux permutations. Malheureusement, je ne vois pas de réduction directe du problème de...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Considérons une permutation σσ\sigma de [1..n][1..n][1..n] . Une inversion est définie comme une paire (i,j)(i,j)(i, j) d'indices tels que i<ji<ji < j et σ(i)>σ(j)σ(i)>σ(j)\sigma(i) > \sigma(j) . Définissez AkAkA_k comme le nombre de permutations de [1..n][1..n][1..n] avec au plus kkk...
Étant donné un ensemble S de matrices de permutation nxn (qui n'est qu'une petite fraction des n! Matrices de permutation possibles), comment pouvons-nous trouver des sous-ensembles de taille minimale T de S tels que l'ajout des matrices de T a au moins 1 dans chaque position? Je suis intéressé par...
Je recherche un algorithme à un passage qui calcule la parité d'une permutation. Je suppose qu'une permutation d'entrée est donnée par le flux π[1],π[2],⋯,π[n]π[1],π[2],⋯,π[n]\pi[1], \pi[2], \cdots, \pi[n] . La sortie doit être la parité de la permutation. La question qui m'intéresse est la...
Quelle est la complexité de calcul du problème suivant: étant donné deux matrices complexes et vérifiez s'il existe une matrice de permutation telle que: n×nn×nn\times nAAABBBPPPB=PAPT.B=PAPT.B = P A P^T. Si cela aide, on peut supposer que et B sont hermitiens (ou même que A et B sont réels et...
Soit le jeu et C (n, k) le jeu de toutes les -combinaisons d'éléments de sans répétition. Soit un -uple dans . On dit qu'une permutation de l'ensemble évite s'il n'y a pas de k-tuple d'entiers tels que { 1 , . . . , n } k [ n ] p = p 1 p 2 . . . p k k C ( n , k ) π : [ n ] → [ n ] [ n ] p i 1 <...
Cette question concerne l'algorithme de Fisher-Yates pour renvoyer un mélange aléatoire d'un tableau donné. La page Wikipedia dit que sa complexité est O (n), mais je pense que c'est O (n log n). Dans chaque itération i, un entier aléatoire est choisi entre 1 et i. La simple écriture de l'entier en...
Étant donné un groupe de permutations sur [ n ] = { 1 , ⋯ , n } , et deux vecteurs u , v ∈ Γ n où Γ est un alphabet fini qui n'est pas tout à fait pertinent ici, la question est de savoir s'il existe des π ∈ G tel que π ( u ) = v où π ( u ) signifie appliquer la permutation π sur u de manière...
Cette question est motivée par ce post, pouvez-vous identifier la somme de deux permutations en temps polynomial? et mon intérêt pour les propriétés de calcul des permutations. Une séquence de différences d'une permutation π de nombres 1 , 2 , … n + 1 est formée en trouvant la différence entre tous...
Existe-t-il des algorithmes de réorganisation des données à optimiser pour la compression? Je comprends que cela est spécifique aux données et à l'algorithme de compression, mais y a-t-il un mot pour ce sujet? Où puis-je trouver des recherches dans ce domaine? Plus précisément, j'ai une liste json...
J'ai 400 balles, dont 100 rouges, 40 jaunes, 50 vertes, 60 bleues, 70 violettes, 80 noires. (les boules de la même couleur sont identiques) j'ai besoin d'un algorithme de brassage efficace, de sorte qu'après le brassage, les balles soient dans une liste, et Les 3 balles consécutives ne sont pas de...
En gros, l'appariement des modèles de permutation traite des problèmes du type suivant: Étant donné les permutations dans et dans , avec , contient-il une sous- séquence de longueur dont les éléments sont ordonnés selon ?ππ\piSnSnS_nσσ\sigmaSmSmS_mm≤nm≤nm\leq nππ\pi ττ\taummmσσ\sigma Par exemple,...
Les algorithmes en temps polynomial sont connus pour trouver des groupes générateurs de groupes de permutation, ce qui est intéressant car nous pouvons alors représenter ces groupes de manière succincte sans renoncer aux algorithmes en temps polynomial pour répondre à de nombreuses questions...