当前位置：文江博客话题详情

从索引生成一个排列

发布于 2025-01-14 00:19:34 字数 91 浏览 3 评论 0原文

是否有一种有效的算法可以从提供的一个索引生成排列？排列不需要有任何特定的顺序，它只需要为每个可能的索引返回每个排列一次。我希望排列的集合是 0~255 之间的所有整数。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

A君 2025-01-21 00:19:34

如果我正确理解这个问题，问题如下：给你两个整数n和k，你想找到k n 整数的第次排列。你并不关心它是第 k 个字典排列，但字典排列更容易，所以让我们坚持下去。

这对于计算来说还算不错。基本排列是1,2,3,4...n。这是k=0 的情况。考虑一下如果你要交换 1 和 2 会发生什么：通过移动 1，你就放弃了 1 在前的每一个排列，并且有 (n-1)! 个排列（因为如果您修复了 1，则可以对 2,3,4..n 进行排列）。因此，该算法如下：

for i from 1 to n:
    j = k / (n-i)! // integer division, so rounded down
    k -= j * (n-i)!
    place down the jth unplaced number

这将迭代地产生第 k 个字典排列，因为它重复地解决具有较小的一组数字来放置的子问题，并一路递减 k。

If I understand the question correctly, the problem is as follows: You are given two integers n and k, and you want to find the kth permutation of n integers. You don't care about it being the kth lexicographical permutation, but it's just easier to be lexicographical so let's stick with that.

This is not too bad to compute. The base permutation is 1,2,3,4...n. This is the k=0 case. Consider what happens if you were to swap the 1 and 2: by moving the 1, you are passing up every single permutation where 1 goes first, and there are (n-1)! of those (since you could have permuted 2,3,4..n if you fixed the 1 in place). Thus, the algorithm is as follows:

for i from 1 to n:
    j = k / (n-i)! // integer division, so rounded down
    k -= j * (n-i)!
    place down the jth unplaced number

This will iteratively produce the kth lexicographical permutation, since it repeatedly solves a sub-problem with a smaller set of numbers to place, and decrementing k along the way.

回复收藏 0 原文

暮色兮凉城 2025-01-21 00:19:34

在 python 模块 more-itertools 中有一个实现： nth_排列。

下面是一个实现，改编自 more_itertools.nth_permutation 的代码：

from sympy import factorial

def nth_permutation(iterable, index):
    pool = list(iterable)
    n = len(pool)
    c = factorial(n)
    index = index % c
    result = [0] * n
    q = index
    for d in range(1, n + 1):
        q, i = divmod(q, d)
        if 0 <= n - d < n:
            result[n - d] = i
        if q == 0:
            break
    return tuple(map(pool.pop, result))

print( nth_permutation(range(6), 360) )
# (3, 0, 1, 2, 4, 5)

There is an implementation in python in module more-itertools: nth_permutation.

Here is an implementation, adapted from the code of more_itertools.nth_permutation:

from sympy import factorial

def nth_permutation(iterable, index):
    pool = list(iterable)
    n = len(pool)
    c = factorial(n)
    index = index % c
    result = [0] * n
    q = index
    for d in range(1, n + 1):
        q, i = divmod(q, d)
        if 0 <= n - d < n:
            result[n - d] = i
        if q == 0:
            break
    return tuple(map(pool.pop, result))

print( nth_permutation(range(6), 360) )
# (3, 0, 1, 2, 4, 5)

回复收藏 0 原文

~没有更多了~