Finding all unique permutations of a set

Hi,

I am working on a project of mine and I am trying to output all distinct combinations of a given set which contains a random number of 0's, 1's, 2's and 3's, in total there must be exactly 22 numbers in a combination.

I found a script from 2013, from someone who asked a similar question, but that one only worked for for example [0 1 0 1]. I got it to work for 22 numbers but I can't get it to work for more than 2 numbers.

I am trying to do output all possible permutations of for example the set [0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 3].

All help is appreciated! :)

This is the script I found and edited and which works (and it's very fast):

c = [0 1];
cc = c(fullfact([2 2 2 2]));
out = cc(sum(cc,2) == 2,:);

A = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1];
n = numel(A);
k = sum(A);
c = nchoosek(1:n,k);
m = size(c,1);
out = zeros(m,n);
out(sub2ind([m,n],(1:m)'*[1 1 1 ...1 1 1],c)) = 1

EDIT: the perm()-command is unable to do the job for 22 numbers, I already tried this.

Answer 1

[John D'Errico]

First, lets see if your task is even possible to do. You would be surprised. Far too often people seem to think they have immensely huge and powerful computers. So, do you? How many possible permutations of that set exist?

Your sample population has 12 zeros, 6 ones, 2 twos, and a 3. That is 21 numbers. To make it 22 numbers as you say you want, I'll add another 2.

S = [0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 3];

How many possible unique permutations are there?

There are factorial(22) permutations, IF all numbers are distinct. But they are not. So we divide by the number of ways we can permute the 12 zeros, as well as the 6 ones, etc.

N = factorial(22)/factorial(12)/factorial(6)/factorial(3)/factorial(1)
N =
   543182640

So, only 543 million possible permutations. Since we need to store those permutations, each permutation requires us to store 22 elements. As well, assume this is a double precision array, so 8 bytes per element. Next, anytime you have a large array of numbers, any computation you do with that array will often create a copy or two. A good rule of thumb is to triple the amount of memory of your largest array to be relatively safe.

N*22*8*3
ans =
          286800433920

Do you have a computer with roughly 300 gigabytes of addressable RAM? Even if you store the numbers in a uint8 array, so 2 bytes per number, you would still want roughly 75 gigabytes of addressable RAM.

Unless you have a large server at your command, I doubt it. And computing all of those permutations will likely not be trivial. Most schemes you find will start with a MUCH larger array, and then throw out the duplicates. And worse, while today you want to solve a problem with 22 elements, tomorrow or next month it will be 30.

The point? While it is a nice idea to try to generate all of those permutations, there are better ways to solve many problems. This is why we use tools like optimizers, which allow you to solve a problem without generating an entire immense search space for a brute force solution. Things that work great for small problems can be easily overwhelmed on large problems.

Answer 2

[sgalzin]

I stumbled on this question because I have similar needs (though with a much more reasonable number of unique permutations). It doesn't take much for unique(perms(x)) to choke and there is some leg room between that and the number of permutations being simply unmanageable (as examplified by John's previous answer). Therefore, I have implemented such a function, please do the calculations for your own usage to make sure it yields feasible sizes (cf. nbTotalPermutations in code below if you need).

Below is an example which, on my computer, will fail using the " unique(perms) " brute-force approach but will succeed with the ad-hoc function. Note that this example only leads to 34,650 unique permutations, unlike the version the OP was asking for (requiring up to 150,570,227,808 permutations in the worst case scenario of, say, [0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3]). Still, the example shows that there are gains to be had for those of us with large numbers of non-unique permutations but decently sized unique permutations.

a = [1,1,1,1,2,2,2,2,3,3,3,3]; % this will succeed for list1 but will be too large (on my computer) for list2
list1 = doPermutations( a );
try
    list2 = unique( perms( a ), 'rows' );
catch e
    list2 = a;
    warning( e.message );
end
fprintf( 'Size: (%d,%d)\n', size( list1 ) );
fprintf( 'Differences between both versions: %d\n', size( [ setdiff(list1,list2,'rows');setdiff(list2,list1,'rows') ], 1 ) );

a = [1,1,1,1,2,2,3,3];  % this leads to reasonable solutions and we show that the function works by comparing it to the brute-force approach.
list1 = doPermutations( a );
try
    list2 = unique( perms( a ), 'rows' );
catch e
    list2 = a;
    warning( e.message );
end
fprintf( 'Size: (%d,%d)\n', size( list1 ) );
fprintf( 'Differences between both versions: %d\n', size( [ setdiff(list1,list2,'rows');setdiff(list2,list1,'rows') ], 1 ) );

function permutations = doPermutations( v )
    u = unique( v );
    n = histcounts( v, numel( u ) );
    nbInts = numel( n );
    nbSlots = numel( v );
    groups = cell( 1, nbInts );
    nbPermutations = ones( 1, nbInts );
    for iInt = 1:nbInts
        groups{ iInt } = nchoosek( 1:nbSlots, n( iInt ) );
        nbPermutations( iInt ) = size( groups{ iInt }, 1 );
        nbSlots = nbSlots - n( iInt );
    end
    nbTotalPermutations = prod( nbPermutations );
    keys = fullfact(nbPermutations);
    permutations = nan( prod( nbPermutations ), sum( n ) );
    for iInt = 1:nbInts
        nanIdx = cumsum( isnan( permutations ), 2 );
        for iElement = 1:n( iInt )
            for iPermutation = 1:nbTotalPermutations
                permutations( iPermutation, find( nanIdx( iPermutation, : ) == groups{iInt}( keys(iPermutation, iInt ), iElement ), 1 ) ) = u( iInt );
            end
        end
    end
end