lexicographic-ordering - 编号排列

Question

给定一个长度为 n 的字母表A = {a,b,c,d,...}，我想得到长度为 r (r < n) 的所有排列。

现在我想对这些排列进行编号，并且应该有一个反向映射。

例如：

A = {a,b,c}, r = 2

ab -> 0
ba -> 1
ac -> 2
ca -> 3
...

我怎样才能做到这一点？我发现它可以解决顺序不变的问题。但我无法通过订单将其应用于这种情况。

有没有一些图书馆在 python 中做它？

Answer 1

大概aa是一个无效的选择。由于您从不同的字母表进行交易，因此每笔交易都会产生一组不相交的排列。您的列表由r! * choose(n,r)which is n!/(n-r)!or n_ror “n 个元素的 k 排列”计算。对这些进行编号的规范方法是按字典顺序排列。

如果我尝试使用通用库生成这些，我会找到一种方法来处理或选择未重复的r元素，然后在该集合上生成所有排列 size r。就编号而言，如果您可以按字典顺序将排列存储在数组中，则可以通过 binsearch 查找索引。可以通过分析来反转映射，但实际上，无论您在这里做什么，都必须具有较小r的 .

快速搜索显示 Pythonitertools为您提供了您需要的两个函数：combinations和permutations.

Answer 2

我们知道有 n 个长度为 1 的排列（其中 n 是字母表的长度）。长度为 r 的排列是所有长度为 r-1 的排列加上字母表中的 n 个元素中的每一个。其中有 n^r 个。

分配 ids 排列很简单，因为生成排列和计数实际上是一回事。

在这里，在 JS 中，我们用任何字符数组计算排列或长度 r。为了说明有关计数的想法，请参见字母表是数字集 '0'='9' 时的输出...

function permute(r, alphabet) {
  if (r === 1) return alphabet
  let result = []
  let r1 = permute(r-1, alphabet)
  for (let p of r1) {
    for (let a of alphabet) {
      result.push(p+a)
    }
  }
  return result
}

const permutations = permute(3, ['a', 'b', 'c', 'd']);
const withIds = permutations.map((value, id) => ({id, value}));
console.log(withIds);

在python中同样的事情......

def permute(r, alphabet):
    if r == 1: return alphabet
    result = []
    r1 = permute(r-1, alphabet)
    for p in r1:
        for a in alphabet:
            result.append(p+a)
    return result