News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Permutation with repetition

Started by mineiro, April 30, 2016, 11:02:21 AM

Previous topic - Next topic

mineiro

Hello everybody, I was a member from this board on the past, my english language continues not good.
I know that have brilhant math Sir's here, and this make myself go back again.

Supose I have 3 elements, A,B,C, and each one have frequency 3,2,1. So, A=3,B=2 and C=1.

I know that I can have 6!/3!*2! == 60 ways to permute these 3 elements.

My question is about an index. Supose that index 1 is AAABBC, so, how can I know the index of BCAABA? Have some formulae or function to do this or I should try brute force?
And if somebody give to me an index, how can I know the sequential elements generated? If I have 60 ways to do, what should be the generated elements to an index like 39?

Can anybody help me to solve this?

Thank so much, I hope everybody here is fine, with peace in mind.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

Zen

MINEIRO,
Well, the obvious question is: index to what ??? Presumably this is an index into a data structure. If this is an index into a member of a data structure, what do you want this data structure to resemble ??? Are you only going to generate it once ???

raymond

I have to assume (which I don't normally like doing) that your indexing starting at 1=AAABBC would continue with all the other combinations starting with "A" before all other combinations starting with "B" or "C".

Those combinations starting with "A" would be followed by combinations of AABBC numbering 5!/2!*2!=30. Any combination starting with "B" would thus start at index 31.

Combinations starting with "B" would be followed by combinations of AAABC numbering 5!/3!=20.
Which would leave combinations starting with "C" starting at index 51.

Combinations starting with "C" would be followed by the AAABB combinations numbering 5!/3!*2!=10, and the last index would be 60 for the CBBAAA listing.

If you look at any group taken at random, you can apply a similar reasoning to determine its index.
Let's use BACABA as an example.

The B... group starts at index 31.
By definition, the BA... group also starts at index 31 and is followed by the remaining AABC which numbers 4!/2!=12.
By definition, the BAA... group also starts at index 31 and is followed by the remaining ABC.
But, the BAB.. group would only start following the BAA... group which numbers 3!=6 and would start at index 31+6=37.
But then the BAC... group would only start following the BAB... group which numbers 3!/2!=3, and would thus start at index 37+3=40, and followed by the remaining AAB
By definition, the BACA.. group also starts at index 40 and is followed by the remaining AB.
By definition, the BACAA. group also starts at index 40 and is followed by the remaining B.

Therefore, the index for BACABA would be 41.

As proof, the index for BACBAA would be 42 and the index for BBAAAC would be 31+12=43.

Have fun.
Whenever you assume something, you risk being wrong half the time.
https://masm32.com/masmcode/rayfil/index.html

mineiro

Hello sir Zen and sir raymond;

Zen, we are talking about anagrams. So the word EGG have 1 letter E and 2 letters G. But this word have 3 letters, so 3!/2!*1!== (3*2*1)/(2*1)*(1) == 3 possibles permutations like, GGE, GEG, EGG. The question is about what index is EGG in that possibilities. Looking now is easy, it's just the 3rd option, so index 3. But, you can see that I have done all possible combinations before say the index?(brute force). I have asked a way to calculate that index on a direct way. I remember you philosophic friend.

raymond, no words to say, thank you, I fully understand your comment, you are the man. Thank you for the examples. Your way appears like an arithmetic coding where ranges of each other are inside ranges of each one. Very nice, you're a smart person. If chucky norris see you he will say sorry and run the most that he can.

I was done a tree where each node hold the elements frequency, so, after each inclusion their respective  frequency is subtracted to generated all possibilities. Your way is better.

Appreciated, be in peace Sir's.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything