编码求有重复排列的索引的数学方法 [英] Coding the mathematical approach for finding index of a permutation that has repetition
本文介绍了编码求有重复排列的索引的数学方法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
如何计算根据具有给定长度和给定不同字符数量的输入字母表排序的字符串列表中元素的索引。
from itertools import product
def bruteforce_item_index(item, alphabet, length, distinct):
skipped=0
for u in product(alphabet, repeat=length):
v = ''.join(u)
if v == item:
return skipped
if len(set(u)) == distinct:
skipped += 1
作为示例
bruteforce_item_index('0123456777', alphabet='0123456789', length=10, distinct=8)
在~1分钟内运行并给出答案8245410。此处的运行时间与给定项的索引成正比。
我想要一个能够在几分之一秒内计算出该索引的高效实现。
换句话说：如何解决this问题？在同一页面上提供了一个数学方法。我希望使用python、Java或C#代码作为解决方案。
推荐答案
在此回答中，我将解释如何获得一个函数，该函数使您能够获得序列中元素的索引，如下所示
print("Item 3749832414 is at (0-based) index %d" %
item_index('3749832414', alphabet='0123456789', length=10, distinct=8))
print("Item 7364512193 is at (0-based) index %d" %
item_index('7364512193', alphabet='0123456789', length=10, distinct=8))
> Item 3749832414 is at (0-based) index 508309342
> Item 7364512193 is at (0-based) index 1005336982
枚举方法
根据您的问题的性质，以递归方式解决它是很有趣的，逐个添加数字并跟踪使用的数字数量。Python提供迭代器，以便您可以逐个生成项，而无需存储整个序列。
基本上所有项都可以排列在一个前缀树中，我们遍历产生叶节点的三个项。
def iter_seq(alphabet, length, distinct, prefix=''):
if distinct < 0:
# the prefix used more than the allowed number of distinct digits
return
if length == 0:
# if distinct > 0 it means that prefix did not use
# enought distinct digits
if distinct == 0:
yield prefix
else:
for d in alphabet:
if d in prefix:
# the number of distinct digits in prefix + d is the same
# as in prefix.
yield from iter_seq(alphabet, length-1, distinct, prefix + d)
else:
# the number of distinct digits in prefix + d is one more
# than the distinct digits in prefix.
yield from iter_seq(alphabet, length-1, distinct-1, prefix + d)
让我们用可以可视化的示例进行测试
list(iter_seq('0123', 5, 1))
['00000', '11111', '22222', '33333']
import numpy as np
np.reshape(list(iter_seq('0123', 4, 2)), (12, 7))
array([['0001', '0002', '0003', '0010', '0011', '0020', '0022'],
['0030', '0033', '0100', '0101', '0110', '0111', '0200'],
['0202', '0220', '0222', '0300', '0303', '0330', '0333'],
['1000', '1001', '1010', '1011', '1100', '1101', '1110'],
['1112', '1113', '1121', '1122', '1131', '1133', '1211'],
['1212', '1221', '1222', '1311', '1313', '1331', '1333'],
['2000', '2002', '2020', '2022', '2111', '2112', '2121'],
['2122', '2200', '2202', '2211', '2212', '2220', '2221'],
['2223', '2232', '2233', '2322', '2323', '2332', '2333'],
['3000', '3003', '3030', '3033', '3111', '3113', '3131'],
['3133', '3222', '3223', '3232', '3233', '3300', '3303'],
['3311', '3313', '3322', '3323', '3330', '3331', '3332']],
dtype='<U4')
清点项目
正如您在上一个问题中注意到的，序列中的项数仅取决于每个字符串的长度、字母表的大小和不同符号的数量。
如果我们查看上面函数的循环，我们只有两种情况，(1)当前数字在前缀中，(2)数字不在前缀中。数字在前缀中出现的次数正好是前缀中不同数字的数量。因此，我们可以添加一个参数used来跟踪已经使用的位数，而不是实际的前缀。现在复杂度从O(length!)到O(2**length)。
此外，我们还使用了lru_cache修饰符，它将记忆这些值，如果参数被重复，则无需调用函数即可返回它们，这使得函数在O(length**2)时间和空间中运行。
from functools import lru_cache
@lru_cache
def count_seq(n_symbols, length, distinct, used=0):
if distinct < 0:
return 0
if length == 0:
return 1 if distinct == 0 else 0
else:
return
count_seq(n_symbols, length-1, distinct-0, used+0) * used +
count_seq(n_symbols, length-1, distinct-1, used+1) * (n_symbols - used)
我们可以确定它与iter_seq
assert(sum(1 for _ in iter_seq('0123', 4, 2)) == count_seq(4, 4, 2))
我们还可以测试它与您手工计算的示例相吻合
assert(count_seq(10, 10, 8) == 1360800000)
索引中的项目
这一部分不是获得最终答案所必需的，但它是一个很好的练习。此外，它将为我们提供一种计算更大的序列的方法，这将是一种繁琐的手工操作。
这可以通过迭代iter_seq给定的次数来实现。此函数通过将给定子树中的叶子数量(由特定调用生成的项目数量)与到所请求索引的距离进行比较来更有效地实现这一点。如果请求的索引距离大于调用产生的项数，则意味着我们完全可以跳过该调用，直接跳到树中的下一个同级项。
def item_at(idx, alphabet, length, distinct, used=0, prefix=''):
if distinct < 0:
return
if length == 0:
return prefix
else:
for d in alphabet:
if d in prefix:
branch_count = count_seq(len(alphabet),
length-1, distinct, used)
if branch_count <= idx:
idx -= branch_count
else:
return item_at(idx, alphabet,
length-1, distinct, used, prefix + d)
else:
branch_count = count_seq(len(alphabet),
length-1, distinct-1, used+1)
if branch_count <= idx:
idx -= branch_count
else:
return item_at(idx, alphabet,
length-1, distinct-1, used+1, prefix + d)
我们可以测试它与iter_seq
for i, w in enumerate(iter_seq('0123', 4, 2)):
assert w == item_at(i, '0123', 4, 2)
给定项目的索引
请记住，我们是在前缀树中行走，给定一个字符串，我们可以直接行走到所需的节点。查找索引的方法是将此路径上留下的所有子树的大小相加。def item_index(item, alphabet, length, distinct, used=0, prefix=''):
if distinct < 0:
return 0
if length == 0:
return 0
else:
offset = 0
for d in alphabet:
if d in prefix:
if d == item[0]:
return offset + item_index(item[1:], alphabet,
length-1, distinct, used, prefix + d)
else:
offset += count_seq(len(alphabet),
length-1, distinct, used)
else:
if d == item[0]:
return offset + item_index(item[1:], alphabet,
length-1, distinct-1, used+1, prefix + d)
else:
offset += count_seq(len(alphabet),
length-1, distinct-1, used+1)
我们可以再次测试这与iter_seq
for i,w in enumerate(iter_seq('0123', 4, 2)):
assert i == item_index(w, '0123', 4, 2)
或者如我在文章开头所承诺的那样查询您给出的示例数字
print("Item 3749832414 is at (0-based) index %d" %
item_index('3749832414', alphabet='0123456789', length=10, distinct=8))
print("Item 7364512193 is at (0-based) index %d" %
item_index('7364512193', alphabet='0123456789', length=10, distinct=8))
> Item 3749832414 is at (0-based) index 508309342
> Item 7364512193 is at (0-based) index 1005336982
奖励：更大的序列
让我们计算UCP3gzjGPMwjYbYtsFu2sDHRE14XTu8AdaWoJPOm50YZlqI6skNyfvEShdmGEiB0的索引
在长度为64和50个不同符号的序列中
item_index('UCP3gzjGPMwjYbYtsFu2sDHRE14XTu8AdaWoJPOm50YZlqI6skNyfvEShdmGEiB0',
alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz',
distinct=50, length=64)
令人惊讶的是10000...000 = 10**110。我怎样才能找到那个特定的字符串？？
这篇关于编码求有重复排列的索引的数学方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
