Thursday, 24 February 2022

Getting permutation index and permutation at index faster than the provided solution

Thanks to this answer, here is how I'm getting permutation index and permutation at an index:

def get_Cl(distinct):
Cl = []
for i in range(1, distinct+1):  # i is distincct
    c = [0] * i + [1, 0]
    C = [c]
    for l in range(2, distinct+1):
        c = [
                c[d] * d + c[d + 1] * (distinct - d)
                for d in range(i + 1)
            ] + [0]
        C.append(c)
    Cl.append(C)
return Cl


def item_index(item, distinct, n_symbols, Cl):
    length = len(item)
    offset = 0
    seen = set()
    for i, di in enumerate(item):
        for d in range(n_symbols):
            if d == di:
                break
            if d in seen:
                # test = Cl[distinct][length - 1 - i][len(seen)]
                offset += Cl[distinct][length - 1 - i][len(seen)]
            else:
                offset += Cl[distinct][length - 1 - i][len(seen) + 1]
        seen.add(di)
    return offset


def item_at(idx, length, distinct, n_symbols, Cl):
    seen = [0] * n_symbols
    prefix = [0] * length
    used = 0
    for i in range(length):
        for d in range(n_symbols):
            if seen[d] != 0:
                branch_count = Cl[distinct][length - 1 - i][used]
            else:
                branch_count = Cl[distinct][length - 1 - i][used + 1]
            if branch_count <= idx:
                idx -= branch_count
            else:
                prefix[i] = d
                if seen[d] == 0:
                    used += 1
                seen[d] = 1
                break
    return prefix


if __name__ == "__main__":
    Cl = get_Cl(300)
    item = item_at(idx=432,length=300,distinct=200, n_symbols=300, Cl=Cl)
    print(item)
    print(item_index(item=item, distinct=200, n_symbols=300, Cl=Cl))

It works fine unless numbers get bigger then it gets very slow. Wondered if it is possible to improve this code like this answer?

The reason I get Cl in a separate line is that for a fixed distinct there will be thousands of calls on item_at and item_index, so the Cl is the same if distinct is the same thus no need for call it for each item_at or item_index.



from Getting permutation index and permutation at index faster than the provided solution

No comments:

Post a Comment