Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Can you clarify your question a little bit? You seem to be asking how to browse through a set of combinations, the easiest of which (in my mind) would be to express the integers 0 to 26 in base 3. But then you give an example at the bottom which I can't quite follow. For example, what is Combination 5? And what combination numbers would "0 0 0" and "1 1 2" be? –  Sp3000 Jan 31 '12 at 8:00
    
This reference may help: Generating the mth Lexicographical Element of a Mathematical Combination:msdn.microsoft.com/en-us/library/aa289166(v=vs.71).aspx –  Emmad Kareem Jan 31 '12 at 8:21
    
crossposted to MO: mathoverflow.net/questions/87116/… –  Ricky Demer Jan 31 '12 at 9:24
    
See whether what you want isn't already at math.stackexchange.com/questions/97813/… –  Gerry Myerson Jan 31 '12 at 12:03
    
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. –  Marc van Leeuwen Jan 31 '12 at 12:43

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.