Generating all combinations (not all permutations) of n characters with length up to n

0
votes

How can we generate all the possible combinations of n characters with length 1 to n in an increasing order of length?

For Example : if n = 4 and characters are 1,2,3,4 we need to generate an array 

1,2,3,4
12,13,14,23,24,34
123, 124, 134, 234
1234

Here n is the variable and user can feed the n characters.

1
algorithmmatlabloopsif-statementcombinations
You can always use nchoosek('1234', k) with a loop on k - Luis Mendo
Luis , thanks !! it works in matlab but I also needed the algorithm for coding it in cpp .I am a beginner in matlab so couldn't get enough from the source code in matlab for the function. - amanized
If you need it in C++ that's a different question altogether. I suggest you post it anew with the C++ tag. Also, people will probably ask what you have tried. You should show your code and where you got stuck or why it doesn't work - Luis Mendo
There's a recursive implementation of nchoosek in the answer here. - beaker

1 Answers

0
votes

There is a bijection between the combinations of up to n elements and the bit masks of length n. A way to solve your problem is to generate all bitsets of length n and sort them by the number of bits they have on. You can use bucket sort for this.

Create n+1 lists corresponding to the numbers from 0 to n. Then iterate over all bitmasks and for each bitmask compute the number of bits that are 1 in it and then add the bitmask in the corresponding list. Using those lists it should be pretty easy to solve the problem.