0

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.

amanized
  • 9
  • 5
  • 2
    You can always use `nchoosek('1234', k)` with a loop on `k` – Luis Mendo Jun 27 '16 at 11:42
  • 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 Jun 27 '16 at 11:52
  • 4
    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 Jun 27 '16 at 11:54
  • There's a recursive implementation of `nchoosek` in the answer [here](http://stackoverflow.com/questions/17624776/matlab-nchoosek-limitation-workaround). – beaker Jun 27 '16 at 14:09

1 Answers1

0

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.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176