算法发现多集置换给予词典指数 [英] Algorithm for finding multiset permutation given lexicographic index

问题描述

我试图找到一个高效的算法来找到一个多重的排列，给出一个索引。

例如：给定 {1，3，3} 。在升序字典顺序所有排列是 {133，313，331} 。这些元素建立索引 {0，1，2} 。鉴于指数= 2 ，结果为331。

<一个href="http://stackoverflow.com/questions/8940470/algorithm-for-finding-numerical-permutation-given-lexicographic-index">I找到一个算法找到一组给定的词典式指数排列。他的方法是有效的：为O（n ^ 2）

不过，该算法在一组适当的测试（如 {1，2，3} ），并在我的测试不正确。我形容他的蟒蛇code在这里，让您可以轻松跟踪。

 从数学进口阶乘，地板＃// Python库
从数学进口阶乘，地板＃// Python库
I = 5＃// i是字典指数（计数从0开始）
N = 3＃// n是排列的长度
p值=范围（1，n + 1个）＃// p是从1到n的列表
对于k的范围（1，N + 1）：＃//ķ从1到n
    D = 1 //因子（NK）＃//使用整数除法（如师+楼）
    打印（P [D]。）
    p.remove（P [D]。）＃//删除由对P [D]。
    I = I％阶乘（NK）＃//减少我对其余数
 

解决方案

 ＃的Python 2
从集合导入计数器
从数学进口阶乘


高清count_permutations（计数器）：
    值= counter.values​​（）
    返回 （
        阶乘（总和（的值））/减少（拉姆达一个，ν：一个*阶乘（v）中，值1）
    ）


高清置换（升，指数）：
    升=排序（升）

    如果没有索引：
        RETURN L

    计数器=计数器（升）
    TOTAL_COUNT = count_permutations（计数器）
    ACC = 0
    为I，V在枚举（1）：

        如果我＆GT; 0和v ==升[I-1]：
            继续

        数= TOTAL_COUNT *计数器[V] / LEN（L）

        如果ACC +计数＆GT;指数：
            返回[V] +排列（L [我] + 1 [I + 1：]，指数 -  ACC）

        ACC + =计

    提高ValueError错误（没有足够的置换）
 

似乎按预期

 在[17]：对于x范围内（50）：打印X，置换（[1，1，2，2，2]，X）
0 [1，1，2，2，2]
1 [1，2，1，2，2]
2 [1，2，2，1，2]
3 [1，2，2，2，1]
4 [2，1，1，2，2]
5 [2，1，2，1，2]
6 [2，1，2，2，1]
7 [2，2，1，1，2]
8 [2，2，1,2，1]
9 [2，2,2，1，1]
10 ------------------------------------------------- --------------------------
ValueError错误回溯（最新最后调用）
[...]
ValueError错误：没有足够的置换
 

时间复杂度：为O（n ^ 2）

I am trying to find an efficient algorithm to find permutation of a multiset, given an index.

Ex: given {1, 3, 3}. All permutations in an ascending lexicographic order are {133, 313, 331}. These elements are indexed as {0, 1, 2}. Given index=2, the result is 331.

I found an algorithm to find permutation of a set given a lexicographic index. His algorithm is efficient: O(n^2).

However, the algorithm is tested on a proper set (e.g. {1, 2, 3}), and not correct on my test. I describe his python code here so that you can easily follow.

from math import factorial, floor #// python library
from math import factorial, floor #// python library
i=5 #// i is the lexicographic index (counting starts from 0)
n=3 #// n is the length of the permutation
p = range(1,n+1) #// p is a list from 1 to n
for k in range(1,n+1): #// k goes from 1 to n
    d = i//factorial(n-k) #// use integer division (like division+floor)
    print(p[d]),
    p.remove(p[d])   #//delete p[d] from p
    i = i % factorial(n-k) #// reduce i to its remainder

解决方案

# Python 2
from collections import Counter
from math import factorial


def count_permutations(counter):
    values = counter.values()
    return (
        factorial(sum(values))/reduce(lambda a, v: a * factorial(v), values, 1)
    )


def permutation(l, index):
    l = sorted(l)

    if not index:
        return l

    counter = Counter(l)
    total_count = count_permutations(counter)
    acc = 0
    for i, v in enumerate(l):

        if i > 0 and v == l[i-1]:
            continue

        count = total_count * counter[v] / len(l)

        if acc + count > index:
            return [v] + permutation(l[:i] + l[i + 1:], index - acc)

        acc += count

    raise ValueError("Not enough permutations")

Seems to work as expected

In [17]: for x in range(50): print x, permutation([1, 1, 2, 2, 2], x)
0 [1, 1, 2, 2, 2]
1 [1, 2, 1, 2, 2]
2 [1, 2, 2, 1, 2]
3 [1, 2, 2, 2, 1]
4 [2, 1, 1, 2, 2]
5 [2, 1, 2, 1, 2]
6 [2, 1, 2, 2, 1]
7 [2, 2, 1, 1, 2]
8 [2, 2, 1, 2, 1]
9 [2, 2, 2, 1, 1]
10---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
[...]
ValueError: Not enough permutations

Time complexity: O(n^2).

这篇关于算法发现多集置换给予词典指数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！