Get Nth combination of a set of elements with loose conditions

1
votes

Given:

  1. A list of symbols of size M
  2. The desired size of combination L
  3. Symbols may occur any number of times in a combination
  4. All permutations of any combination of the symbols must be taken into the account

Example: for a list of symbols (a, b, c), and L=4, all of the combinations (a, a, a, a), (a, b, a, c), (a, c, b, b) and so on are valid. For the lack of a better term, I called this "loose combinations".

The particular ordering of the combinations is not important. Being given the combination index N, the algorithm should return a unique combination from the set of possible combinations that satisfy the conditions. My guess is that the most natural order would be if we consider the combinations as numbers of radix M and length L, so that the normal number order would apply, but that is not strictly necessary to follow.

What is the algorithm to find the Nth combination?

I'm not sure how to find the answer myself, and have been searching if there was an answer for this particular set of conditions elsewhere, but did not find it. All the questions that I find are not interested in combinations with repeating elements like (a, a, b, b) and combinations with rearranged order, like (a, a, b, c) and (a, b, c, a) or (a, c, a, b) are treated as the same combination.

1
mathpermutationcombinatorics
Is there an ordering in the combinations? I cannot see any. If not there is no distinct 'N'-th element, but all and none of the elements are the 'N'-th one. Also how is this question linked to Java or Kotlin? If there is a naive ordering the question becomes "How to use nested for loop" - leonardkraemer
@leonardkraemer thanks for the comment! I have edited the question to mention it about the order. - noncom
@noncom Oh, I thought this connection to be the hard part. I'll reemphasize my answer to go into more depth on the base-M part. - Hermann Döppes
You are aware, that you can only find unique combinations for N < M^Lright? - leonardkraemer
@leonardkraemer yes, of course :) this I have managed to figure it out, but thanks for mentioning it! - noncom

1 Answers

2
votes

As you figured out already, you are essentially interested in enumerating the numbers of length up to L in base M. So, a solution might look like this:

  • Define a bijection {0, …, M-1} -> Symbols, i.e. enumerate your symbols.
  • For any non-negative integer N < M^L, determine its base M representation.
    • Easily done by repeated modulo M and rounded down division by M.
    • Without loss of generality, this has length M by adding leading zeroes as needed.
  • Use your bijection to convert this list of digits 0 to M-1 to a loose combination of symbols.

So, let's go into detail on this part:

Easily done by repeated modulo M and rounded down division by M.

Pseudocode:

int a[L];
for int i from 0 to L-1 do
    a[i] = N % M; // Should go from 0 to M-1
    N = N / M; // Rounded down, of course
done