Let's say you have 4 red balls, 2 blue balls and 1 green ball. That is 7 balls, and considering a ball can't be distinguished from another if it has the exact same color, this makes for a total of (7!)/(4!2!1!) = 105 possible permutations (Source).
Meaning, say we associate red with 0, blue with 1 and green with 2, there are 105 ways to arrange the [0, 0, 0, 0, 1, 1, 2] array.
More generally, this can be seen as n balls, m ball types, and nₖ balls of type k with 1 <= k <= m and (n1+n2+...+nk) = n, having (n!)/(n1!*n2!*...*nk!) possible permutations.
Is there an algorithm that can get a unique number from a given permutated array, and get this permutated array back from that exact, same, unique number (also refered to as index)?
The number, in the case of the given example, must be a value between 0 and (n!)/(n1!*n2!*...*nk!) - 1.
With the example I've given, this would be between 0 and 104, but with different values, it could be from 0 to any very high number, which the algorithm must support.
The algorithm must not require calculating all (nor most) possible permutations.
While I'm taking an easy example with 105 permutations here, I'd like this to be usable for something that could have 30 trillions of them, which we obviously can't possibly all calculate, so your algorithm's complexity very much matters here.
I don't care about the order of the permutations, the only thing that matters is that you can get a unique index from each one, and get the permutation back from its index.
Fast permutation -> number -> permutation mapping algorithms
How can I generate all permutations of length n from a set of k elements?
How to find the index of a k-permutation from n elements?
Generate one permutation from an index
These questions only feature arrays where there is one of each permutable element (meaning n! possible permutations for an array of size n). I'd like the possibility to have an individual, fixed, >1 amount of each element (significantly reducing the number of possible permutations for that same array of size n if some elements are present multiple times).
Coding the mathematical approach for finding index of a permutation that has repetition
While this question features the possibility of having multiple of one element, it's not a fixed amount per element, significantly increasing the number of possible permutations.
Generate permutations of indices of identical items
This question asks to generate every single possible permutation, which I'd like to avoid (as with huge arrays, it would be too much to compute), and its answer even uses a library for this.
Find the index of a given permutation in the sorted list of the permutations of a given string
This question does not account for duplicate elements. There will be some permutations that will be obtainable from multiple indices, which is not what I'm looking for. Additionally, the answer provided does not include a way to go back from an index to a permutation, only the other way around.
Algorithm for finding multiset permutation given lexicographic index
This answers part of the question, but only works one way. I'm looking for an algorithm that works both ways.
Considering all of these questions are on SO, were well-received, weren't deemed as off-topic, and do not necessarely ask for a specific programming language implementation (including the most recent one), it makes sense for this one to be on-topic, too.
Besides, I'm asking for one, specific, reversable algorithm, in the context of writing software.
The structure has changed. Nowadays you have Math SE and Computer Science SE.
ComputerScience.SE is older than all questions I have linked, Math.SE is older than all but one of them.
Math.SE says that "Algorithm implementation/design" (emphasis mine) belongs to SO.
Ranking ("indexing") in lexicographic order, the index of a permutation is the number of smaller permutations. A smaller permutation has an equal prefix followed by a suffix whose first element is smaller, and whose rest is in any order.
My rank function goes through the suffixes from short to long. Its n and ways are the length of the suffix and the number of ways that suffix can be permuted. For your example, they end up as 7 and 105. My freq tracks the values in the suffix and their frequencies. For each suffix with first element x, I consider every smaller element y from the suffix as replacement, and add to the index the number of ways the rest of the suffix can be permuted.
def rank(perm):
"""Return the index of the given permutation."""
freq = Counter()
n = 0
ways = 1
index = 0
for x in reversed(perm):
freq[x] += 1
for y in freq:
if y < x:
index += ways * freq[y] // freq[x]
n += 1
ways = ways * n // freq[x]
return index
First a simple solution. Instead of trying to "invert the code" of rank, I just start with the smallest permutation and progressively make it bigger with swaps, using rank to tell me when I went too far.
def unrank_simple(index, elements):
"""Return the permutation of the elements that has the given index."""
perm = sorted(elements)
n = len(perm)
for i in range(n):
for j in range(i + 1, n):
perm[i], perm[j] = perm[j], perm[i]
if rank(perm) > index:
perm[i], perm[j] = perm[j], perm[i]
break
return perm
The below function is fast for quite large cases. It works similar to rank. First it computes all frequencies and the total number of ways. Then it computes one permutation element at a time, from first to last. It updates n, freq and ways so they reflect the remaining suffix of the permutation.
def unrank(index, elements):
"""Return the permutation of the elements that has the given index."""
freq = Counter()
n = 0
ways = 1
for x in sorted(elements):
freq[x] += 1
n += 1
ways = ways * n // freq[x]
perm = [None] * n
for i in range(n):
for x in freq:
ways_with_x_here = ways * freq[x] // n
if index < ways_with_x_here:
break
index -= ways_with_x_here
perm[i] = x
ways = ways_with_x_here
freq[x] -= 1
if not freq[x]:
del freq[x]
n -= 1
return perm
I've tested with all 105 permutations of your example. Abbreviated output, showing my three functions correctly rank and unrank all permutations:
0 [0, 0, 0, 0, 1, 1, 2] True True True
1 [0, 0, 0, 0, 1, 2, 1] True True True
2 [0, 0, 0, 0, 2, 1, 1] True True True
3 [0, 0, 0, 1, 0, 1, 2] True True True
4 [0, 0, 0, 1, 0, 2, 1] True True True
...
100 [2, 1, 0, 0, 0, 0, 1] True True True
101 [2, 1, 0, 0, 0, 1, 0] True True True
102 [2, 1, 0, 0, 1, 0, 0] True True True
103 [2, 1, 0, 1, 0, 0, 0] True True True
104 [2, 1, 1, 0, 0, 0, 0] True True True
Here are times for ranking and unranking five random permutations. For your question's example, for the larger case from your comment, and for an even much larger case with 1000 elements:
elements: [0, 0, 0, 0, 1, 1, 2]
ways: 105
rank unrank
Test #1: correct 0.0 ms 0.0 ms
Test #2: correct 0.0 ms 0.0 ms
Test #3: correct 0.0 ms 0.0 ms
Test #4: correct 0.0 ms 0.0 ms
Test #5: correct 0.0 ms 0.0 ms
elements: [1] * 500 + [2, 3, 4, 5, 6, 7]
ways: 16292279781882720
rank unrank
Test #1: correct 0.3 ms 0.5 ms
Test #2: correct 0.4 ms 0.5 ms
Test #3: correct 0.4 ms 0.5 ms
Test #4: correct 0.3 ms 0.5 ms
Test #5: correct 0.4 ms 0.5 ms
elements: random.choices(range(100), k=1000)
ways: 255162988647149562479012494411356412582180138200423158945380311225856966307407159167529717311901033020388338741195219463559379392323469500678211728725796590317647593303012144893491277456812722847744479351186896996819090854205008161083160385760927158443815073936379337020933153530051495041333488065069224485483771507620316400979506030893191352578031604610948496856618359745997931939987962450897672043160187946818640050712888098145229124145993708164358381529092692821325916456392152922693370897149951514523769128512800091260868624598513768575355846676767810543733865729360105929911935549844199905957438160062288007288875965042155604055693371904064005108330882066911410177240192625559883669891971814817429195121579118550674229346268287984254565519201350047598084385594228018996474797411379620782415246464680714591658564805229395802087064866823472583306304428519079819975792761118058478244194783455122673876174140278366969319694137793177005431406267646069555561145766245935367879696377335588050947200024794769361191216173874884824514763816170735422795629903086661384991761719994555418700393307880335808855693637029592515547953477340839433783056354855225133333398345805539080546742255989446421151482598292970089834959005517579559854706508484264709968086752092586061091687092165980288664009132767191301069307588375093280649481073370158262409514731715150009588035860451264976525804479972264281889576300376295733365110077320395581619728696594342920963226714939247906918693436233368885136213662070258251260289179427851437841908761339478645034630405011183533970180815093413161869517661858201953335435260437278285932471966175053646232160937160252321600366648164451961949387592973036276490790074394814256349825171223006016995957718161642053070654653015744325335759233986466299969036481195763505220099744393890306803630080000000000000000000000000000000000000000000000000000000000000000000000000000000000000
rank unrank
Test #1: correct 94.0 ms 93.4 ms
Test #2: correct 96.2 ms 96.4 ms
Test #3: correct 92.8 ms 91.0 ms
Test #4: correct 92.1 ms 93.8 ms
Test #5: correct 95.0 ms 92.3 ms
The solutions, correctness testing, and benchmarks:
from collections import Counter
import random
from time import perf_counter as time
def rank(perm):
"""Return the index of the given permutation."""
freq = Counter()
n = 0
ways = 1
index = 0
for x in reversed(perm):
freq[x] += 1
for y in freq:
if y < x:
index += ways * freq[y] // freq[x]
n += 1
ways = ways * n // freq[x]
return index
def unrank_simple(index, elements):
"""Return the permutation of the elements that has the given index."""
perm = sorted(elements)
n = len(perm)
for i in range(n):
for j in range(i + 1, n):
perm[i], perm[j] = perm[j], perm[i]
if rank(perm) > index:
perm[i], perm[j] = perm[j], perm[i]
break
return perm
def unrank(index, elements):
"""Return the permutation of the elements that has the given index."""
freq = Counter()
n = 0
ways = 1
for x in sorted(elements):
freq[x] += 1
n += 1
ways = ways * n // freq[x]
perm = [None] * n
for i in range(n):
for x in freq:
ways_with_x_here = ways * freq[x] // n
if index < ways_with_x_here:
break
index -= ways_with_x_here
perm[i] = x
ways = ways_with_x_here
freq[x] -= 1
if not freq[x]:
del freq[x]
n -= 1
return perm
def test(elements):
# Compute all unique permutations for testing
from itertools import permutations
perms = sorted(map(list, set(permutations(elements))))
# Test ranking and unranking
for index, perm in enumerate(perms):
print(
index,
perm,
rank(perm) == index,
unrank_simple(index, elements) == perm,
unrank(index, elements) == perm
)
print()
test([0, 0, 0, 0, 1, 1, 2])
def count_ways(elements):
n = 0
freq = Counter()
ways = 1
for x in elements:
n += 1
freq[x] += 1
ways = ways * n // freq[x]
return ways
def benchmark(elements):
print('\n\nelements:', elements)
elements = eval(elements)
print('ways:', count_ways(elements))
print('\n rank unrank')
for i in range(1, 6):
perm = elements.copy()
random.shuffle(perm)
t0 = time()
index = rank(perm)
t1 = time()
perm2 = unrank(index, elements)
t2 = time()
print(f'Test #{i}: {'correct' if perm2 == perm else 'wrong'} {(t1 - t0) * 1e3 :5.1f} ms {(t2 - t1) * 1e3 :5.1f} ms')
benchmark('[0, 0, 0, 0, 1, 1, 2]')
benchmark('[1] * 500 + [2, 3, 4, 5, 6, 7]')
benchmark('random.choices(range(100), k=1000)')