Algorithm to list all unique permutations of numbers contain duplicates

Question

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?

Preserve

Since there are n! permutations of n distinct integers, you cannot do better than O(n!) if you are required to enumerate them. Also note that the presence of duplicates is irrelevant since the process of removing the duplicates takes a negligible amount of time compared to enumerating the permutations. – Heppman

@veredesmarald. Yes, I am trying to reduce the time complexity to O(n!). – Preserve

1. next_permutation (in C++ STL) visits every permutation exactly once even when there are duplicates. 2. The space requirement alone is O(nn!), not O(n!). 3. Inserting all n! permutations in an STL set would take O(n! log(n!)) = O(nn!*logn) – Scrimmage

@Scrimmage I believe the point of the excercise is to implement next_permutation. Also I perhaps should have qualified that I was talking about time complexity only, and I would just store them in a list (since the next perm algo already excludes the duplicates). – Heppman

@bloops. 1. Next_permutation makes the problem less fun. 2. You are right, the overall time complexity using set is O(n! lg(n!)). – Preserve

Answer 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

Heppman

Updated: I originally misread the question and thought duplicates were supposed to be discarded before computing the permutations. – Heppman

The next_permutation is the point. And there is no homework in summer:) – Preserve

@zwx Where I live, it's winter. :) I have added some links to next perm algorithms, if you run into any specific difficulties I'll be happy to help but otherwise I don't see any merit in me retyping the algorithms here. – Heppman

The complexity of the "regular" next_permutation algorithm is O(1) amortized over all permutations. So if you are visiting all permutations, that's optimal. – Scrimmage

@Scrimmage It appears you are correct. I didn't know that, thanks! – Heppman

Answer 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

Bialy

Answer 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]

Hairy

Answer 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]

Photic

Answer 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.

Heaney

Answer 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

Neologism

Answer 7

A simple and short C++ implementation of @verdesmarald's solution:

vector<vector<int>> permuteUnique(vector<int>& nums) {

    vector<vector<int>> res;
    const auto begin = nums.begin();
    const auto end = nums.end();
    std::sort(begin, end);

    do
    {
        res.push_back(nums);
    } 
    while (std::next_permutation(begin, end));

    return res;
}

I think time complexity is: n*log(n) + m * ComplexityOf(next_permutation) where n is the total number of elements, m is unique elements and complexity of next_permutation is O(1) amortized. Or so they say: The amortized complexity of std::next_permutation?

Burbank