How to Generate a Permutations or Combinations of N Rows in M Columns

How to generate a permutations or combinations of n rows in m columns?

Combinations:

SELECT T1.x, T2.x
FROM your_table T1
JOIN your_table T2
ON T1.x < T2.x

Permutations:

SELECT T1.x, T2.x
FROM your_table T1
JOIN your_table T2
ON T1.x != T2.x

I am assuming that the values in the original table are unique.

To generalize for larger values of m you need to add more joins.

All permutations where 0/1 are added to each column of a dataframe row

You can use the itertools package to generate all possible combinations:
itertools.product produces an iterable which you can cast to a list and then Dataframe (suggestions to prevent casting are very welcome)

x = pd.DataFrame(list((itertools.product([0, 1], repeat=5))))
x.head()
Out[46]: 
    0  1  2  3  4
0   0  0  0  0  0
1   0  0  0  0  1
2   0  0  0  1  0
3   0  0  0  1  1
4   0  0  1  0  0
5   0  0  1  0  1
6   0  0  1  1  0
7   0  0  1  1  1

in a next step you can just add your list to each row of the the dataframe

comb = x + [1,2,3,4,5]
comb.head()
Out[47]: 
    0  1  2  3  4
0   1  2  3  4  5
1   1  2  3  4  6
2   1  2  3  5  5
3   1  2  3  5  6
4   1  2  4  4  5
5   1  2  4  4  6
6   1  2  4  5  5

How to create all permutations of a 2-column cell-array?

2^m is actually a binary number, so we can use those to create linear indices. You'll get an array containing 1s and 0s, something like [1 1 0 0 1 0 1 0 1], which we can treat as column "indices", using a 0 to indicate the first column and a 1 to indicate the second.

m = size(A, 1);
% Build all binary numbers and create a logical matrix
bin_idx = dec2bin(0:(2^m -1)) == '1';

row = 3;  % Loop here over size(bin_idx,1) for all possible permutations
linear_idx = [find(~bin_idx(row,:)) find(bin_idx(row,:))+m];
A{linear_idx}  % the combination as specified by the permutation in out(row)

On my R2007b version this runs virtually instant for m = 20.

NB: this will take m * 2^m bytes of memory to store bin_idx. Where that's just 20 MB for m = 20, that's already 30 GB for m = 30, i.e. you'll be running out of memory fairly quickly, and that's for just storing permutations as booleans! If m is large in your case, you can't store all of your possibilities anyway, so I'd just select a random one:

bin_idx = rand(m, 1);  % Generate m random numbers
bin_idx(bin_idx > 0.5) = 1;  % Set half to 1
bin_idx(bin_idx < 0.5) = 0;  % and half to 0

---

Old, slow answer for large m

perms()¹ gives you all possible permutations of a given set. However, it does not take duplicate entries into account, so you'll need to call unique() to get the unique rows.

unique(perms([1,1,2,2]), 'rows')

ans =

     1     1     2     2
     1     2     1     2
     1     2     2     1
     2     1     1     2
     2     1     2     1
     2     2     1     1

The only thing left now is to somehow do this over all possible amounts of 1s and 2s. I suggest using a simple loop:

m = 5;
out = [];

for ii = 1:m
    my_tmp = ones(m,1);
    my_tmp(ii:end) = 2;
    out = [out; unique(perms(my_tmp),'rows')];
end

out = [out; ones(1,m)];  % Tack on the missing all-ones row

out =
     2     2     2     2     2
     1     2     2     2     2
     2     1     2     2     2
     2     2     1     2     2
     2     2     2     1     2
     2     2     2     2     1
     1     1     2     2     2
     1     2     1     2     2
     1     2     2     1     2
     1     2     2     2     1
     2     1     1     2     2
     2     1     2     1     2
     2     1     2     2     1
     2     2     1     1     2
     2     2     1     2     1
     2     2     2     1     1
     1     1     1     2     2
     1     1     2     1     2
     1     1     2     2     1
     1     2     1     1     2
     1     2     1     2     1
     1     2     2     1     1
     2     1     1     1     2
     2     1     1     2     1
     2     1     2     1     1
     2     2     1     1     1
     1     1     1     1     2
     1     1     1     2     1
     1     1     2     1     1
     1     2     1     1     1
     2     1     1     1     1
     1     1     1     1     1

NB: I've not initialised out, which will be slow especially for large m. Of course out = zeros(2^m, m) will be its final size, but you'll need to juggle the indices within the for loop to account for the changing sizes of the unique permutations.

You can create linear indices from out using find()

linear_idx = [find(out(row,:)==1);find(out(row,:)==2)+size(A,1)];
A{linear_idx}  % the combination as specified by the permutation in out(row)

Linear indices are row-major in MATLAB, thus whenever you need the matrix in column 1, simply use its row number and whenever you need the second column, use the row number + size(A,1), i.e. the total number of rows.

Combining everything together:

A = cell(8, 2);
for row = 1:8
    for col = 1:2
        A{row, col} = rand(3, 3);
    end
end

m = size(A,1);
out = [];

for ii = 1:m
    my_tmp = ones(m,1);
    my_tmp(ii:end) = 2;
    out = [out; unique(perms(my_tmp),'rows')];
end

out = [out; ones(1,m)];

row = 3;  % Loop here over size(out,1) for all possible permutations
linear_idx = [find(out(row,:)==1).';find(out(row,:)==2).'+m];
A{linear_idx}  % the combination as specified by the permutation in out(row)

---

¹ There's a note in the documentation:

perms(v) is practical when length(v) is less than about 10.

Generating certain permutations

I guess this satisfies all your requirements. Even the order seems correct to me:

M=3;N=3;
mat1=eye(M+1);
vectors=mat2cell(repmat(1:M+1,N,1),ones(N,1),[M+1]);

Super-efficient cartesian product, taken from here:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
n = numel(vectors); %// number of vectors
combs = cell(1,n); %// pre-define to generate comma-separated list
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1}); %// the reverse order in these two
%// comma-separated lists is needed to produce the rows of the result matrix in
%// lexicographical order
combs = cat(n+1, combs{:}); %// concat the n n-dim arrays along dimension n+1
combs = reshape(combs,[],n); %// reshape to obtain desired matrix
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    

V=cell(size(combs,1),1);
for i=1:size(combs,1)
    for j=1:size(combs,2)
        V{i,1}=[V{i,1};mat1(combs(i,j),:)];
    end
end

Outputs:

M=2,N=2;

V=

[1,0,0;1,0,0]
[1,0,0;0,1,0]
[1,0,0;0,0,1]
[0,1,0;1,0,0]
[0,1,0;0,1,0]
[0,1,0;0,0,1]
[0,0,1;1,0,0]
[0,0,1;0,1,0]
[0,0,1;0,0,1]

M=3;N=3;  %order verified for the indices given in the question

V(1)  = [1,0,0,0; 1,0,0,0; 1,0,0,0] 
V(2)  = [1,0,0,0; 1,0,0,0; 0,1,0,0]
V(3)  = [1,0,0,0; 1,0,0,0; 0,0,1,0]
V(4)  = [1,0,0,0; 1,0,0,0; 0,0,0,1]
V(5)  = [1,0,0,0; 0,1,0,0; 1,0,0,0]
        ...
V(8)  = [1,0,0,0; 0,1,0,0; 0,0,0,1]
V(9)  = [1,0,0,0; 0,0,1,0; 1,0,0,0]
        ...
V(16) = [1,0,0,0; 0,0,0,1; 0,0,0,1]
V(17) = [0,1,0,0; 1,0,0,0; 1,0,0,0]
        ...
V(64) = [0,0,0,1; 0,0,0,1; 0,0,0,1]

---

Related Topics