Mapping and Recovering Combinations: A Challenge in Combination Theory

In summary: 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 1233) add the ordered key to a dictionary to indicate that you found a number with that key4) count the different keys in the dictionary which should be 120for 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
  • #1
raminee
12
2
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.
 
Last edited:
Physics news on Phys.org
  • #2
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.
 
  • #3
jedishrfu said:
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.
 
  • #4
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.)
 
  • #5
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
 
  • #6
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.
 
  • #7
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.
 
  • #8
raminee said:
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.
 
  • #9
  • Like
Likes FactChecker
  • #10
@raminee

You might be interested in this 20 year old post I made to Are Technica inquiring about a reverse Combinadic. I've spoken (in email) once or twice to McCaffrey.

Long story short, the answer is in the Ars Thread if trying to make the index.

https://arstechnica.com/civis/threa...lumn-on-pascals-triangle.374437/#post-8163078


also, here are of my more recent work based on combination / permutations. and yes, you can use it to compress data (sometimes)

some permutations:


parsing compression level, or if not-compressable with default data input:


[Personal e-mail address redacted by the Mentors]
 
Last edited by a moderator:
  • #11
@raminee

If you look close enough (in attached image), you can see where compression becomes achievable. not a lot mind you, but there is the possibility or running cycles (compress the compressed data).

Really the hold up is the input data. If all data was 45% pop-count and below, or 55% pop-count and above, you could compress it all. The tricky part is that most data is 46% to 54% pop-count :P That is when dealing with data that is 1023 bits wide (size per data chunk / sector). I have implemented variable sector size versions of this BTW.

For larger bit widths, like 8191 bits wide... it is closer to: 48% pop-count and below, or 52% pop-count and above being (minimally) compressible.

1023_compress.jpg
 
  • #12
What a strange thread. The OP asked exactly the same question 7 months previously, and was given the answer 24 hours later that they needed to search for "combinadics".

raminee said:
OK I think I found the answer.

By looking back at your own thread?

I don't know why I bother :wink:
 

Similar threads

  • Programming and Computer Science
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Math Proof Training and Practice
3
Replies
102
Views
7K
  • General Math
Replies
1
Views
760
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
27
Views
3K
  • Math Proof Training and Practice
2
Replies
67
Views
8K
  • Introductory Physics Homework Help
Replies
11
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
Back
Top