Mapping and Recovering Combinations: A Challenge in Combination Theory

[raminee]

TL;DR Summary

How to come up with an index for a set of number selections in combination theory

Hello All,

Not sure if this belongs in general math but lets start here and see where it takes us.

In mathematics, a combination is a way of selecting items from a collection where the order of selection does not matter.

As an example , say we have digits 1 to 10. And we want to select 3 digits. A digit can not be repeated.
Combination theory tells us that there would be M! / ( (M-N)! * N! ). [ (!) means factorial]
So in this example we would get 10! / ( (10-3)! * 3! ) = 120 combinations of 3 different digit numbers.

Lets take the combination as an index indication of the 3 digits produced.
So if we have 120 possibilities then one could say :

digits 1,2,3 ==> index 1
digits 1,2,4 ==> index 2
digits 1,2,5 ==> index 3
---
----
digits 8,9,10 ==> index 120

My question or challenge is 2 folds:

A) Given 3 numbers how can one map it to one of the indices 1 to 120 ??

B) If an index is given how to recover the 3 digits mapped to this index ?
i.e. reverse of (A)

So to be clear I am looking for an algorithm that would define the process in A and B.

Thx
R.

 

[jedishrfu]

Is this a homework assignment?

or are youy looking for a python script that does A and B?

Something like this (in psuedo code):
1) program counts from 0 to 999 ie 000, 001, 002, ...123, ...231 ... 321 ...
2) orders the digits in the three digit number in increasing order 123 is okay but 321, 231, 321... are reordered to 123 basically mapping them to 123
3) add the ordered key to a dictionary to indicate that you found a number with that key
4) count the different keys in the dictionary which should be 120

for B you've lost information when mapping to 123 and so you can only speculate that given the 123 key it may represent 123, 132, 213, 231, 312, or 321.

 

[raminee]

Are youy looking for a python script that does A and B

Something like this (in psuedo code):
1) program counts from 0 to 999 ie 000, 001, 002, ...123, ...231 ... 321 ...
2) orders the digits in the three digit number in increasing order 123 is okay but 321, 231, 321... are reordered to 123 basically mapping them to 123
3) add the ordered key to a dictionary to indicate that you found a number with that key
4) count the different keys in the dictionary which should be 120

for B you've lost information when mapping to 123 and so you can only speculate that given the 123 key it may represent 123, 132, 213, 231, 312, or 321.

Hi,
I am looking for the psuedo code.
In your example numbers that are the same are not allowed ! So 000, 223 and so on are not valid combinations.

The order of the numbers is not important. What is important that the index points to a combination of 3 digit code.

Also I used a simple example in my previous post where the total digits were 10 and numbers selected were 3 which results in 120 possibilities. I can easily make a table lookup of each possibility and assign an index to map and index and do a reverse look up to recover the 3 digits. However the project I am working on is more complicated and the combination possibility is 10 numbers selected from 64 possibilities. This results in something like 2 to power of 37. Huge number. so table look ups is not a possibility.

 

[FactChecker]

Are you looking for a way to store all combinations in an array with index, i, like $C_1, C_2, ..., C_n$ and know how to find a particular combination in the array. Like, find the index, i, where $C_i$ contains 6,3,4?
I have often used hash tables to implement something like the "6,3,4" -> i mapping. (Although I usually used the hash table to look up some information other than an index.)

 

[raminee]

I am not looking to store any combinations.
In my project I find the combinations C1,C2 and C3.
For simplicity we can order these so that, in your example say 6,3,4 is in ascending order, 3,4,6.
What I need is to come up with an index that is mapped only to the combinations of C1,C2,C3 regardless of the order.

In my project I select 10 numbers out of 64 digits. That is 151,473,214,816 combinations. It is almost impossible to have a table of any sort to store these combinations. But the 10 numbers can be stored as a 37 bit info.
Log2(151,473,214,816) = 37.14 bits.

So for any 3 digit combinations of c1,c2,c3 out of (10 digits) once ordered, say in ascending order, one should be able to map it to an index from 1 to 120.
I need the magic process that does this.
And the reverse process too.

Let me put it this way,

Suppose I want to send the 3 digits over to you.
Rather than sending you the 3 digits (C1,C2,C3) I send you the index (any number from 1 to 120) and once you decode the index you can recover the 3 digits back.

So what is the process of encoding C1,C2,C3 to a unique index value
and
How to decode the index to recover C1,C2,C3

 

[FactChecker]

This may be a side thought. You can just send the numbers over. If you need to make the message smaller, there are lossless compression algorithms (although I don't know how much they would help in this situation). If you need to encode them, you should be aware that a function code to an index is the type of code that can be broken or discovered by hacking.

 

[raminee]

Believe it or not the index approach is the most optimized way of preserving the combinations info.

I know there is a procedure to encode and decode any combination sets into a unique index.
I had come across this problem a long time ago and I remember reading about it in a paper.
But I can not find the paper no matter how much I have searched for it.

I thought I post here to see if anyone can point me in the right direction.

 

[PeroK]

Believe it or not the index approach is the most optimized way of preserving the combinations info.

I know there is a procedure to encode and decode any combination sets into a unique index.
I had come across this problem a long time ago and I remember reading about it in a paper.
But I can not find the paper no matter how much I have searched for it.

I thought I post here to see if anyone can point me in the right direction.

You need a way to count the missing numbers. Let's take 2, 4, 8 as an example.

With combinations of 3 numbers from 1-10, we have 36 combinations that start with 1. So, for example, 2, 3, 4 would code to 37. Then, we have to count how many start 2,3. That's another 7. So, 2,4,5 would code to 44. Finally, we see that 2,4,8 codes to 47.

It doesn't look too hard to turn that into an algorithm for this particular case (or to generalise to combinations of 3 numbers from $n$). Trying to generalise to $k$ numbers from $n$ looks more difficult.

 

[raminee]

OK I think I found the answer.

For those of you that are interested here are the 2 correct terminologies for this:
Lexicographical Elements of Combinations
and
Combinadic.

The links to the following two sites is where it is all explained.

https://planetcalc.com/8594/

https://jamesmccaffrey.wordpress.co...lement-of-a-combination-using-the-combinadic/

The 2nd link is the best explanation from the originator/inventor of the actual solution by James D. McCaffrey.

Thumbs up to him !

R.