Algorithm to list all unique permutations of numbe

问题:

The problem is: Given a collection of numbers that might contain duplicates, return all unique permutations.

The naive way is using a set (in C++) to hold the permutations. This takes O(n! × log(n!)) time. Is there better solution?

回答1:

The simplest approach is as follows:

1. Sort the list: O(n lg n)
2. The sorted list is the first permutation
3. Repeatedly generate the "next" permutation from the previous one: O(n! * <complexity of finding next permutaion>)

Step 3 can be accomplished by defining the next permutation as the one that would appear directly after the current permutation if the list of permutations was sorted, e.g.:

1, 2, 2, 3
1, 2, 3, 2
1, 3, 2, 2
2, 1, 2, 3
2, 1, 3, 2
2, 2, 1, 3
...

Finding the next lexicographic permutation is O(n), and simple description is given on the Wikipedia page for permutation under the heading Generation in lexicographic order. If you are feeling ambitious, you can generate the next permutation in O(1) using plain changes

回答2:

1) Some variation on backtracking/recursive search will usually solve this sort of problem. Given a function to return a list of all permutations on (n-1) objects, generate a list of all permutations on n objects as follows: for each element in the list insert the nth object in all possible positions, checking for duplicates. This isn't especially efficient, but it often generates straightforward code for this sort of problem.

2) See Wikipedia at http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

3) Academics have spent a lot of time on details of this. See section 7.2.1.2 of Knuth Vol 4A - this is a large hardback book with the following brief table of contents on Amazon:

Chapter 7: Combinatorial Searching 1

7.1: Zeros and Ones 47

7.2: Generating All Possibilities 281

回答3:

You should read my blog post on this kind of permutation (amongst other things) to get more background - and follow some of the links there.

Here is a version of my Lexicographic permutations generator fashioned after the generation sequence of Steinhaus–Johnson–Trotter permutation generators that does as requested:

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'  

The output from the above program is the following for example:

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]

回答4:

This one I invented after thinking about how I have written out permutations by hand and putting that method in code is shorter and better:

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 increments the permutation vector to find all of them. It also correctly handles repeat letters.
• test prints out all permutations and their count for the test string. It also makes sure that if you request lexicographic ordering that the sort before and sort after methods are the same. This should be True since the original string is ordered and the increment permutation function transforms the string into the next lexicographic string by the given alphabet.

This script can be run at the command prompt by:

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

回答5:

I had slightly improved Paddy3118's solution, so it's now non-recursive, lazy-evaluated (completely based on generators) and faster approximately by 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. I have noticed Paddy3118 had made his implementation use generators as well, while I have been working against implementation in the blog post, which is more memory intensitive. I am posting this anyway, as this version might be considered cleaner.

回答6:

A recursive version. This computes for n!/(m*k!) (m number of sets of chars, k number of repeated chars in each 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;
}

Hope this helps