Formua to browse through combinations

[rockoroll]

Hi,

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

 

[chiro]

Hey rockoroll and welcome to the forums.

To answer your question you may want to tell us any constraints that you have. For this post I will go through the most general case which focuses on generating all possible permutations for a set of objects.

Lets say you have n objects. The number of arrangements for n distinct objects (can be numbers or any other object) is n!. If you don't know what a factorial it is basically the product of all positive whole numbers (greater than zero) up to n.

Examples are 3! = 3x2x1 = 6 and 6! = 6x5x4x3x2x1 = 720. Also 0! is defined to be 1.

So in terms of computer code you will need to create all possible permutations (arrangements) given an array of n objects.

One way to do this is to use a recursive algorithm.

The recursive algorithm will basically fix a permutation based on the number of things that are fixed as well as the values corresponding to the objects that are fixed.

So for example what we want to do is to have a function that calculates the permutations of say 3 objects (O1,O2,O3) when the first object is fixed with value v.

So let's say we have v = 01. Then we call the routine again to find all possible permutations with values 01,02 and 01,03. The recursive function will terminate when we only have room for 1 space, since we will only have 1 way of filling that space.

Now I don't want to just give you a routine, so I'll ask you to develop some ideas for how you would construct it and give you any hints that you need.

But the general form of the function will have the following argument list:

void ConstructPermutation(array permutationlist, int numFixedArguments, OutputStructure& outputs, ConstructionOptions& permutation Options);

where the permutationlist is the actual list of objects you wish to permute, numFixedArguments is the number of fixed arguments that you are using and the other variables relate to storing the results (if you want to do that) as well as other options that will be related to constraints for permutation generation.

Also with regards to implementation, if would be wise if you considered that for large computations it would be benefecial to not just throw all your data on the stack and only pass things once that need to be passed to stop you getting things like stack overflows and massive computation times.

 

[Edgardo]

One way is to just count upwards:
111, 112, 113,
121, 122, 123,
131, 132, 133,
211, 212, 213,
221, 222, 223,
231, 232, 233,
311, 312, 313,
321, 322, 323,
331, 332, 333

You add 1 to the last digit and if it is 3, switch to 1 and increase the left digit by 1.
For example 113 becomes 121.

The same applies to the second digit: If it is a 3 and you add 1, then switch it to 1 and add 1 to the first digit. Example: 133 becomes 211.


Another way is to draw trees (see also attachment).

 

[rockoroll]

Thanks for answering!

I'm not sure if I'm following you but I will try to figure it out.

I don't know what more I can tell about the problem.

I will have objects that can have values and the number of values will always be the same for all the objects. I would like to render a list with paging possibilities(first next 1 2 3 4 5 previous last). How will I know which combination I have when clicking for example 4?

What I will know is the number of objects, the number of different values the objects can have and the total number of combinations.

Given the example in my first post, if I know that I'm on combination (1 2 3), clicking next would give me (1 3 1) with what Edgardo suggest which I don't see any problems with. But if I'm on combination (1 2 3) and I click page 4, what will the combination be then?

 

[rockoroll]

The objects are the same type of objects and the values they can hold I guess will be int. Wheather there are 2 or 10 objects the objects will always have the same values between themselves wheather the values will be (1,2,3) or (1,2,3,4,5).

 

[Bill Simpson]

Think about this example for a few minutes.

You have 3 objects and each has 10 values. Number the values 0,1,...9 instead of 1,2,...10.

Now your combinations are
0,0,0
0,0,1
0,0,2
...
9,9,9
If you got rid of the commas you have
000
001
002
...
999
Do you perhaps see integers from 0 to 999 there? Do you think "base 10"? Can you see how to get from integer to combination with say 745? Perhaps using divide and modulus (or mod)? And how to get to next and previous? If you had 7 objects instead of 3, but they still had values 0,1,...9 do you see how this would be similar? See if you can firmly get all this clearly understood with 10 values and base 10.

After that think "base 3." That has nothing to do with 3 object, that has to do with 3 values for each object. See if you can relate each of those sentences in the previous paragraph to something that only has "digits" 0,1,2. How do you count in that? How do you get digits in base 3 with the math you have available?

 

[pbuk]

Most of the answers given here refer to permutations not combinations. Generating combinations (or permutations) is a computational problem, and the solution is an algorithm rather than a formula. Google 'combinations algorithm' and you will find what you want - there is a really neat recursive solution to generate all the combinations at once; if (due to memory or speed constraints) you need to generate them iteratively it is a bit more complex.