编码用于查找具有重复的排列索引的数学方法
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# 代码作为解决方案。
如果我们从集合 {a, b, c, d, e, f} 中选择 3 个符号，则有 20 种可能的组合。我们可以将这些组合记录在一个整数中如：
{a, b, c} => 1
{a, b, d} => 2
{a, b, e} => 3
...
{d, e, f} => 20
那么当我们从集合中选择完3个符号后，就会有3^6种可能的排列。那么我们可以用12位表示。
以{a,b,c}为例，表示可以是：
aaaaaa => 00 00 00 00 00 00
aaaaab => 00 00 00 00 00 01
aaaaac => 00 00 00 00 00 10
...
cccccb => 10 10 10 10 10 01
cccccc => 10 10 10 10 10 10
然后你可以使用一个整数和 12 位二进制的组合来索引你的排列。
你可以试试Factorial number system. This is pretty complicated to explain, but it helps you to solve the problem with O(1) time. This is Project Euler's Lexicographic permutations.
它通过索引找到一个排列。也许你可以通过排列查找索引来重写它。
public static String lexicographicPermutation(String str, int n) {
long[] fact = new long[str.length()];
List<Character> letters = new ArrayList<>(str.length());
for (int i = 0; i < str.length(); fact[i] = i == 0 ? 1 : i * fact[i - 1], i++)
letters.add(str.charAt(i));
letters.sort(Comparator.naturalOrder());
n--;
StringBuilder buf = new StringBuilder(str.length());
for (int i = str.length() - 1; i >= 0; n %= fact[i], i--)
buf.append(letters.remove((int)(n / fact[i])));
return buf.toString();
}
在这个答案中，我将解释如何获得一个函数，该函数将使您能够获取序列中元素的索引，如下所示
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 装饰器，它将记住这些值并 return 它们，如果参数重复，则无需调用该函数，这使得该函数在 O(length**2) 时间内变为 运行 并且space.
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)
或者查询您在 post
开头承诺的示例号码
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。我怎样才能找到那个特定的字符串？？
如何计算根据具有给定长度和给定不同字符数的输入字母表排序的字符串列表中元素的索引。
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# 代码作为解决方案。
如果我们从集合 {a, b, c, d, e, f} 中选择 3 个符号，则有 20 种可能的组合。我们可以将这些组合记录在一个整数中如：
{a, b, c} => 1
{a, b, d} => 2
{a, b, e} => 3
...
{d, e, f} => 20
那么当我们从集合中选择完3个符号后，就会有3^6种可能的排列。那么我们可以用12位表示。 以{a,b,c}为例，表示可以是：
aaaaaa => 00 00 00 00 00 00
aaaaab => 00 00 00 00 00 01
aaaaac => 00 00 00 00 00 10
...
cccccb => 10 10 10 10 10 01
cccccc => 10 10 10 10 10 10
然后你可以使用一个整数和 12 位二进制的组合来索引你的排列。
你可以试试Factorial number system. This is pretty complicated to explain, but it helps you to solve the problem with O(1) time. This is Project Euler's Lexicographic permutations.
它通过索引找到一个排列。也许你可以通过排列查找索引来重写它。
public static String lexicographicPermutation(String str, int n) {
long[] fact = new long[str.length()];
List<Character> letters = new ArrayList<>(str.length());
for (int i = 0; i < str.length(); fact[i] = i == 0 ? 1 : i * fact[i - 1], i++)
letters.add(str.charAt(i));
letters.sort(Comparator.naturalOrder());
n--;
StringBuilder buf = new StringBuilder(str.length());
for (int i = str.length() - 1; i >= 0; n %= fact[i], i--)
buf.append(letters.remove((int)(n / fact[i])));
return buf.toString();
}
在这个答案中，我将解释如何获得一个函数，该函数将使您能够获取序列中元素的索引，如下所示
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 装饰器，它将记住这些值并 return 它们，如果参数重复，则无需调用该函数，这使得该函数在 O(length**2) 时间内变为 运行 并且space.
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)
或者查询您在 post
开头承诺的示例号码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。我怎样才能找到那个特定的字符串？？