0
$\begingroup$

Can anyone give me an idea of how to be able to browse through a set of combinations?

Lets say that I have 3 objects that can hold 3 different values and I want to browse through these. How do I know which is the next combination? I will always know how many values every object can hold and they can always hold the same number of values and therefore I also know total number of combinations. So if I am on combination (3, 2, 1), how do I know that the next combination is (3, 2, 2)?

Object O1 O2 O3

Comb. 1. 1 1 1 Comb. 2. 2 1 1 Comb. 3. 2 2 1 . . . . Comb. 27. 3 3 3

  • 0
    What you _seem_ to be asking for is multi-combinations: choosing a fixed number of $k$ elements from a given set with $n$ elements, where an element can be chosen more than once but order of choice is not taken into account. There are $\tbinom{n+k-1}k$ of those and they are in bijection with the corresponding ordinary (non-repeating) combinations of the $n+k-1$-element set. In any case your examples involve repetitions of the same element. You need to formulate your question precisely if you want to get a useful answer.2012-01-31

1 Answers 1

1

If you are looking just for an enumeration, a simple idea that usually works is define a natural order on standardized representations of what you want to enumerate, and think of a method to find the next element in that ordering. For instance if you want to generate $k$-multi-combinations represented as weakly decreasing lists of $k$ numbers, and you want to do so in lexicographic order, then you can proceed as follows. In most cases you can just advance the last number, but if it is equal to the number before it, then this is forbidden (the result would not be weakly decreasing). So you can try to advance the before-last element, unless it too is blocked by the one before it. Eventually you will find an element that can be advanced, unless all elements are already at the maximal value and there is no next element to move to at all. Once you have advanced one element in the list, don't forget to reset all elements after it to the minimal possible value, in order to be sure you get the next multi-combination in lexicographic order.