Algorithme pour la liste de tous unique de permutations des nombres contenir des doublons

Le problème est le suivant: étant Donné un ensemble de chiffres qui pourraient contenir des doublons, le retour de tous unique de permutations.

Le naïf façon est d'utiliser un ensemble (en C++) pour contenir les permutations. Cela prend O(n! × log(n!)) temps. Est-il la meilleure solution?

Puisqu'il y a n! permutations de n distincts entiers, vous ne pouvez pas faire mieux que O(n!) si vous êtes tenu de les énumérer. Notez également que la présence de doublons est pas pertinent étant donné que le processus de suppression de doublons prend une quantité négligeable de temps par rapport à l'énumération des permutations.
Oui, je suis en train d'essayer de réduire le temps de la complexité à O(n!).
Sons devoirs-ey.
1. next_permutation (en C++ STL) visites chaque permutation exactement une fois, même quand il y a des doublons. 2. L'espace exigence seul est O(nn!), pas de O(n!). 3. En insérant l'ensemble des n! les permutations dans un STL jeu de prendre en O(n! log(n!)) = O(nn!*logn)
Je crois que le point de l'exercice est de mettre en œuvre next_permutation. Aussi, je devrait peut-être se sont qualifiés dont je parlais du temps de la complexité seule, et je voudrais juste de les stocker dans une liste (puisque la prochaine perm algo déjà exclut les doublons).

OriginalL'auteur stackunderflow | 2012-07-11

4

L'approche la plus simple est la suivante:
1. Trier la liste: O(n lg n)
2. La liste triée est la première permutation
3. Générer à plusieurs reprises de la "prochaine" de permutation de la précédente: O(n! * <complexity of finding next permutaion>)
L'étape 3 peut être accompli par la définition de la prochaine permutation que celui qui apparaît directement après la permutation si la liste des permutations de tri, par exemple:
```
1, 2, 2, 3
1, 2, 3, 2
1, 3, 2, 2
2, 1, 2, 3
2, 1, 3, 2
2, 2, 1, 3
...
```
La recherche de la prochaine permutation lexicographique est O(n), et de la simple description est donnée sur la page de Wikipedia pour la permutation de sous la rubrique Génération dans l'ordre lexicographique.
Si vous vous sentez ambitieux, vous pouvez générer le prochain permutation en O(1) à l'aide de plaine les changements

Mise à jour: au départ, j'avais mal lu la question et de la pensée, les doublons ont été censés être jetés avant de calculer les permutations.
Le next_permutation est le point. Et il n'y a pas de devoirs en été:)
Là où j'habite, c'est l'hiver. 🙂 J'ai ajouté quelques liens à la prochaine perm algorithmes, si vous rencontrez des difficultés particulières, je serai heureux de vous aider, mais sinon je ne vois pas le mérite de me retaper les algorithmes d'ici.
La complexité de la "régulière" next_permutation algorithme est O(1) amorti sur toutes les permutations. Donc, si vous êtes en visite à toutes les permutations, ce qui est optimal.
Il semble que vous êtes correct. Je ne le savais pas, merci!

OriginalL'auteur verdesmarald
2

1) variation sur un retour en arrière/recherche récursive sera généralement résoudre ce genre de problème. Étant donné une fonction pour renvoyer une liste de toutes les permutations sur (n-1) objets, de générer une liste de toutes les permutations de n objets de la façon suivante: pour chaque élément dans la liste insérer le nième objet dans toutes les positions possibles, de la vérification de doublons. Ce n'est pas particulièrement efficace, mais il génère souvent une simple code pour ce genre de problème.

2) Voir Wikipedia à http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

3) les Universitaires ont passé beaucoup de temps sur les détails de cette. Voir la section 7.2.1.2 de Knuth Vol 4A - c'est un grand livre relié avec la brève suivante table des matières sur Amazon:

Chapitre 7: Combinatoire De La Recherche 1

7.1: les Zéros et les uns 47

7.2: Générer Toutes Les Possibilités 281

OriginalL'auteur mcdowella

Vous devriez lire mon blog sur ce genre de permutation (entre autres choses) pour obtenir plus d'arrière-plan - et suivez les liens.

Ici est une version de mon Lexicographique permutations générateur constitué d'après la génération de la séquence de Steinhaus–Johnson–Trotter permutation des générateurs, comme demandé:

def l_perm3(items):
    '''Generator yielding Lexicographic permutations of a list of items'''
    if not items:
        yield []
    else:
        dir = 1
        new_items = []
        this = [items.pop()]
        for item in l_perm3(items):
            lenitem = len(item)
            try:
                # Never insert 'this' above any other 'this' in the item 
                maxinsert = item.index(this[0])
            except ValueError:
                maxinsert = lenitem
            if dir == 1:
                # step down
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem, -1, -1)
                                 if i <= maxinsert]:
                    yield new_item                    
            else:    
                # step up
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem + 1)
                                 if i <= maxinsert]:
                    yield new_item                    
            dir *= -1

from math import factorial
def l_perm_length(items):
    '''\
    Returns the len of sequence of lexicographic perms of items. 
    Each item of items must itself be hashable'''
    counts = [items.count(item) for item in set(items)]
    ans = factorial(len(items))
    for c in counts:
        ans /= factorial(c)
    return ans

if __name__ == '__main__':
    n = [0, 1, 2, 2, 2]
    print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
    for i, x in enumerate(l_perm3(n[:])):
        print('%3i %r' % (i, x))
    assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'

La sortie à partir du programme ci-dessus est la suivante par exemple:

Lexicograpic Permutations of 5 items: [0, 1, 2, 2, 2]
  0 [0, 1, 2, 2, 2]
  1 [0, 2, 1, 2, 2]
  2 [2, 0, 1, 2, 2]
  3 [2, 0, 2, 1, 2]
  4 [0, 2, 2, 1, 2]
  5 [2, 2, 0, 1, 2]
  6 [2, 2, 0, 2, 1]
  7 [0, 2, 2, 2, 1]
  8 [2, 0, 2, 2, 1]
  9 [2, 2, 2, 0, 1]
 10 [2, 2, 2, 1, 0]
 11 [2, 1, 2, 2, 0]
 12 [1, 2, 2, 2, 0]
 13 [2, 2, 1, 2, 0]
 14 [2, 2, 1, 0, 2]
 15 [1, 2, 2, 0, 2]
 16 [2, 1, 2, 0, 2]
 17 [2, 1, 0, 2, 2]
 18 [1, 2, 0, 2, 2]
 19 [1, 0, 2, 2, 2]

OriginalL'auteur Paddy3118

0

Ce un j'ai inventé après avoir réfléchi à la façon dont j'ai écrit les permutations par la main et de mettre de la méthode dans le code est plus court et mieux:
```
def incv(prefix,v):
  list = []
  done = {}
  if v:
    for x in xrange(len(v)):
      if v[x] not in done:
        done[v[x]] = 1
        list = list + incv(prefix+v[x:x+1],v[:x] + v[x+1:])
  else:
    list.append(''.join(prefix))
  return list

def test(test_string,lex_ord=False):
  if lex_ord:
    test_string = [x for x in test_string]
    test_string.sort()
  p = incv([],[x for x in test_string])
  if lex_ord:
    try_p = p[::]
    try_p.sort()
    print "Sort methods equal ?", try_p == p
  print 'All', ','.join(p), "\n", test_string, "gave", len(p), "permutations"

if __name__ == '__main__':
  import sys
  test(sys.argv[1],bool(sys.argv[2] if len(sys.argv) > 2 else False))
```
Notes
- incv incrémente le vecteur de permutation pour trouver tous. Il a également gère correctement répétez les lettres.
- test imprime toutes les permutations et leur nombre pour la chaîne de test. Il s'assure également que si vous demandez lexicographique de la commande que le tri avant et tri après les méthodes sont les mêmes. Cela devrait être Vrai depuis que la chaîne d'origine est ordonné et l'incrément de permutation fonction transforme la chaîne dans la prochaine lexicographique de la chaîne par l'alphabet.
Ce script peut être exécuté à partir de l'invite de commande par:

python script.py [test_string] [optional anything to use lexicographic ordering]

OriginalL'auteur Cris
0

J'avais légèrement améliorée Paddy3118 de la solution, donc il est maintenant non-récursive, lazy-évalué (complètement basé sur les générateurs) et plus rapide d'environ 30%.
```
def _handle_item(xs, d, t):
    l = len(xs)

    try:
        m = xs.index(t)
    except ValueError:
        m = l

    if d:
        g = range(l, -1, -1)
    else:
        g = range(l + 1)

    q = [t]
    for i in g:
        if i <= m:
            yield xs[:i] + q + xs[i:]

def _chain(xs, t):
    d = True

    for x in xs:
        yield from _handle_item(x, d, t)

        d = not d

def permutate(items):
    xs = [[]]

    for t in items:
        xs = _chain(xs, t)

    yield from xs
```
P. S. j'ai remarqué Paddy3118 avait fait sa mise en œuvre utilisation de générateurs ainsi, alors que j'ai travaillé sur la mise en œuvre dans le billet de blog, qui est plus de mémoire intensitive. Je suis ce détachement de toute façon, cette version pourrait être considéré comme plus propre.

OriginalL'auteur toriningen

Une version récursive. Ce calcule n!/(m*k!) (m nombre de jeux de caractères, k nombre de caractères répétés dans chaque set:

#include<iostream>
#include<cstring>

using namespace std;

const int MAX_CHARS_STRING=100;
int CURRENT_CHARS=0;
char STR[MAX_CHARS_STRING];

void myswap(int i, int j){
    char c=STR[i];STR[i]=STR[j];STR[j]=c;
}

bool IstobeExecuted(int start,int position){
    if(start==position)
        return true;
    for(int i=position-1;i>=start;i--){
        if(STR[i]==STR[position])
            return false;
    }
    return true;
}

void Permute(int start, int end,int& perm_no){
    if(end-start<=1){
        if(STR[end]==STR[start]){
            cout<<perm_no++<<") "<<STR<<endl;
            return;
        }
        cout<<perm_no++<<") "<<STR<<endl;
        myswap(start, end);
        cout<<perm_no++<<") "<<STR<<endl;
        myswap(start,end);
        return;
    }
    for(int i=start; i<=end;i++){
        if(!IstobeExecuted(start,i)){
            continue;
        }
        myswap(start,i);
        Permute(start+1,end,perm_no);
        myswap(start,i);
    }
}


int main(){
    cin>>STR;int num=1;
    Permute(0,strlen(STR)-1,num);
    return 0;
}

Espère que cette aide

OriginalL'auteur Fooo

Vous devez vous connecter pour publier un commentaire.