Generating permutations, combinations and subsets

general
, ,
1

Suppose I have an array of N integers. I want to display all possible permutations, combinations and subsets of the N integers. Is there an efficient way to do these 3? What are bitset and binary method of counting and if they are one of the ways, how do I use them to implement them?

Manually, this is what I am able to think of. For permutations and combinations,

I fix the 1st element and find all possible permutations/combinations of the remaining N-1 elements. To do so, I fix the 2nd element as well, and find all possible permutations/combinations of the remaining N-2 elements. And so on. I am quite sure this leads to a recursive solution.

For subsets,

For each element I can have 2 values - 0 and 1. 0 means I don’t choose it in my subset. 1 means I choose it in my subset. I think this is what is related to the binary and bitset stuff.

Unfortunately, I am unable to implement my intuitions. Could someone please guide me in the right direction to implement them. A pseudocode would be great!

Sorry for being such a bother. Thanks in advance.

2

I python it is very simple job by using In-build functions:

Assume array=[1,2,3]

For permutations:



from itertools import permutations

print list(permutations(array))

For combinations or subsets:



from itertools import combinations

for i in range(len(array)):

print list(combinations(array,i))

If you want algorithm:
Then for combination or subset try this:

Generate binary numbers upto 2^(len(array))
Example"
For the elements [1, 2, 3]
000 will give    []
001 will give    [3]
010 will give    [2]
011 will give    [2, 3]
100 will give    [1]
101 will give    [1, 3]
110 will give    [1, 2]
111 will give    [1, 2, 3]
3

For subset:
There can be recursive way which is more or less the brute force way. Just a small piece of code here:
PS: path dis an array which will keep your element in the subset, idx is the index for this path array. Try visualizing it by drawing the recursive tree.

void subset(int n, int idx, int path[], int a[], int start)
{
  if(idx==n)
  {
    // this implies this we have considered all elements.
     print the path array here
  }
  if(start>n)
    return;

   // either dont consider the array element a[start]
    // so here, just do the recursive call
     subset(n,idx,path,a,start+1); // notice the change in the function call. Only start gets incremented. The idx and path array remains same
     path[idx]=a[start]; // i.e. we consider the element a[start] in the subset
     subset(n, idx+1,a,start+1);
}

Another approach is there using bits which is well explained here. Also, one more way of printing all the subsets which is however, of the same complexity. But its generally used in printing all k-size subsets of the given set. We basically use bitmasking. The main idea is we find the lowest n-bit number with k-bits set. lets say, we want to find subsets of size 2 of the array whose size is say 5(1,2,3,4,5), of the given array. Then, my lowest n-bit number with 2 bits set is: 00011. Every i’th bit set as 1 denotes inclusion of a[i] element and 0 denotes ignoring the same element. Thus this number represents the set: (4,5). We’ll now find the next higher number with same bits set which is 00101 which represents the set (3,5). Find next higher and repeat till the maximum value you can have. Using this code also, we can find all subsets. See here.

For permutations:
This may be an inefficient approach, but lets say, I have an undirected graph which has n nodes and n*n edges i.e. every node connecting other, n is the length of my array. Then all permutation are just all my dfs traversals of this graph. However there exists a solution using backtracking i.e.I am fixing an element at the first position, recursive for n-1. The pseudocode goes like:

void permutation(int n, int a[], int path[], int idx, int start)
{
   if(start==n)
   {
      // base case, all elements have been considered.
       print the path array here
       return;
   }

   // now at this position idx lets say we had one element but we can have any element from a[start...n]
   for(int j=start;j<=n;j++)
   {
     // interchange the element at path[idx] and a[start]
     // do the recursive call
     // revert the change made above
   }
}

This is explained here with a recursion tree. Using STL, you can do the same easily with an add-on. The function next_permutation will generate the next permutation of the given string.

Taking as a string:

cin>>str;
sort(str,str+length_of_string);
do{
 cout<<str<<endl;
}while(next_permutation(str,str+length_of_string);

And you used permutations/combinations. Did you mean they are same? I seriously don’t think so. Permutations refers to:

all possible arrangements of the given array

and combinations are :

the way of selecting members from a group such that the order of selection doesn't matter. This suggests that, if we are given an array of size n, then we can select all subsets(explained above) of the array i.e. select a set of 1(nC1) element or 2 elements(nC2) and so on..

Hope it clears…