我有一个关于组合学的问题，特别是排列和字典索引。我在过去计算了给定字典索引的集合的排列，但这些是没有重复的排列。
现在我想用重复计算给定字典索引的排列。我的问题是我不知道如何通过重复来处理排列的字典索引。
假设我有以下一组元素“{A,B,C,D,E,F,G,H}
我想计算其中 20 个元素的排列，其字典索引为n; n是 64 位数字。如何确定字典索引？我还能使用阶乘基础方法吗？
问问题
296 次
2 回答
1
假设您有 8 个元素（如您的示例中），这意味着您需要 3 位作为索引。要定义长度为 20 的排列，您需要3*20=60位。
所以整数值v将[0,2^60)定义所有具有重复的排列，其中v & 7将是排列中第一项的索引，(v & (7 << 3) >> 3)- 第二个元素的索引，依此类推......
于 2013-01-28T05:42:15.193 回答
0
你的集合的大小是 8，你的长度是 20，所以总共有 r 8^20 个排列。如果你想计算第n个排列，你可以简单地逐位确定。即如果 n 小于 7^20，则第 1 位为“A”，如果 n 在 [7^20, 2*7^20) 等范围内，则为“B”。
于 2013-01-28T05:14:48.070 回答