我正在尝试想出一种方法来获取重新排列字符串的所有可能方法的列表,以便获得所需的字符串(最终帮助破解柱状换位密码)。
例如,要将“abaca”重新排列为“cabaa”,您可以将原始字符串的索引 3、0、1、2、4 处的字符(按此顺序)放入新字符串中。但是 3,0,1,4,2 和 3,2,1,0,4 等...也可以。
print get_rearrangement_indices("abaca", "cabaa")
>>> [(3, 0, 1, 2, 4), (3, 0, 1, 4, 2), (3, 2, 1, 0, 4), (3, 2, 1, 4, 0), (3, 4, 1, 0, 2), (3, 4, 1, 2, 0)]
我想避免暴力破解所有可能的排列,因为当你有一个由“abcdef”组成的字符串并且你想把它变成“fedcba”时,必须有一个更聪明的方法,但我有一个心理障碍试图解决它。这是我到目前为止所拥有的:
def get_rearrangement_indices(in_string, out_string):
old_indices_to_new = {}
for i, char in enumerate(in_string):
old_indices_to_new[i] = get_indices_of_element(out_string, char) # where get_indices_of_element("abaca", "a") gives you all the indices where there is an "a" i.e. 0,2,4
unique_tuples = set([v for k,v in old_indices_to_new.items()])
new_indices_to_old = defaultdict(tuple)
for unique_tuple in unique_tuples:
for k,v in old_indices_to_new.items():
if not k in new_indices_to_old[v]:
new_indices_to_old[v] += (k,)
print old_indices_to_new # {0: (1, 3, 4), 1: (2,), 2: (1, 3, 4), 3: (0,), 4: (1, 3, 4)}
old_indices_to_new = {v:k for k,v in new_indices_to_old.items()} # Can't decide if this or the old one is easier to work with
print old_indices_to_new # {(3,): (0,), (0, 2, 4): (1, 3, 4), (1,): (2,)}
# itertools
# ???
return profit
请您参考如下方法:
您可以分别排列每个字母的索引。
from itertools import permutations, product
from collections import defaultdict
def get_rearrangement_indices(in_string, out_string):
indices = defaultdict(list)
for i, c in enumerate(in_string):
indices[c].append(i)
for perms in product(*map(permutations, indices.values())):
inds = {c: iter(p) for c, p in zip(indices, perms)}
yield tuple(next(inds[c]) for c in out_string)
演示:
>>> list(get_rearrangement_indices("abaca", "cabaa"))
[(3, 0, 1, 2, 4), (3, 0, 1, 4, 2), (3, 2, 1, 0, 4), (3, 2, 1, 4, 0), (3, 4, 1, 0, 2), (3, 4, 1, 2, 0)]
>>> list(get_rearrangement_indices("aabb", "abab"))
[(0, 2, 1, 3), (0, 3, 1, 2), (1, 2, 0, 3), (1, 3, 0, 2)]
