如何生成一个列表,其中的元素与所需列表的距离固定
How to generates a list which elements are at a fix distance from a desired list
我有一个可能性列表和一个期望的输入:
possibles = [20, 30, 40, 50, 60, 70, 80, 100]
desired = [20, 30, 40]
我想生成收盘价列表。示例:
# Distance of 1 (i.e. 1 element changes to a close-by)
[30, 30, 40]
[20, 40, 40]
[20, 30, 30]
[20, 30, 50]
# Distance of 2:
[40, 30, 40]
[30, 30, 50]
[30, 40, 40]
...
我当前的版本一次只改变一个元素,因此,一旦距离超过 1,我就会缺少很多组合。
def generate_close_by(possibles, desired):
for k in range(1, 4):
for i, elt in enumerate(desired):
id = possibles.index(elt)
new = desired[:]
if id < len(possibles)-k-1:
new[i] = possibles[id+k]
yield (new)
if id > k:
new[i] = possibles[id-k]
yield (new)
# Output
[30, 30, 40]
[20, 40, 40]
[20, 30, 50]
[20, 30, 30]
[40, 30, 40]
[20, 50, 40]
[20, 30, 60]
[50, 30, 40]
[20, 60, 40]
[20, 30, 70]
我很确定应该已经存在一个模块来执行这种迭代(itertools?),你能告诉我写函数吗?
谢谢。
编辑:
尝试更新...
我正在尝试生成一个与 desired 大小相同的列表,其中每个元素对应于我必须移动 desired 元素的程度。
desired = [20, 30, 40]
# Distance of 1:
distance = [1, 0, 0]
distance = [0, 1, 0]
distance = [0, 0, 1]
distance = [-1, 0, 0]
distance = [0, -1, 0]
distance = [0, 0, -1]
然后计划尝试创建新列表,如果不能(越界),它就继续。尚未奏效,但可能是个好方法。
是的,您是对的,itertools
在这里非常有用。你想要的是找到 possibles
列表中所有具有重复项的所需长度的子集,而执行此操作的函数是 itertools.product
from itertools import product
possibles = [20, 30, 40, 50, 60, 70, 80, 100]
desired = [20, 30, 40]
def fake_hamming(cur, desired, possibles):
assert len(cur) == len(desired)
hamm = 0
for i in range(len(cur)):
assert cur[i] in possibles
assert desired[i] in possibles
hamm += abs(possibles.index(cur[i]) - possibles.index(desired[i]))
return hamm
def generate_close_by(desired, possibles, dist):
all_possible_lists = product(possibles, repeat=len(desired))
return [l for l in all_possible_lists if fake_hamming(l, desired, possibles) == dist]
print(generate_close_by(desired, possibles,1))
>>> [(20, 20, 40), (20, 30, 30), (20, 30, 50), (20, 40, 40), (30, 30, 40)]
Edit 好了,更改了产品的组合(请参阅下面的@tobias_k 评论),这里还有 fake_hamming
函数 xD
确实对于大列表来说它会很慢,但这是最通用的方法
def distribute(number, bucket):
if bucket == 1:
yield [number]
if number != 0:
yield [-1 * number]
elif number == 0:
yield [0]*bucket
else:
for i in range(number+1):
for j in distribute(number-i, 1):
for k in distribute(i, bucket-1):
yield j+k
def generate(possibles, desired, distance):
for index_distance_tuple in distribute(distance, len(desired)):
retval = desired[:]
for i, index in enumerate(index_distance_tuple):
if index + i < 0 or index + i >= len(possibles):
break
retval[i] = possibles[index + i]
else:
yield retval
对于距离 1:
for i in generate(possibles, desired, 1):
print(i)
输出:
[30, 30, 40]
[20, 40, 40]
[20, 20, 40]
[20, 30, 50]
[20, 30, 30]
对于距离 2 :
for i in generate(possibles, desired, 2):
print(i)
输出:
[40, 30, 40]
[30, 40, 40]
[30, 20, 40]
[30, 30, 50]
[30, 30, 30]
[20, 50, 40]
[20, 40, 50]
[20, 40, 30]
[20, 20, 50]
[20, 20, 30]
[20, 30, 60]
[20, 30, 20]
您可以尝试递归方法:跟踪剩余距离并仅生成相关元素的组合。
def get_with_distance(poss, des, dist, k=0):
if k < len(des):
i = poss.index(des[k])
for n in range(-dist, dist+1):
if 0 <= i + n < len(poss):
for comb in get_with_distance(poss, des, dist - abs(n), k+1):
yield [poss[i + n]] + comb
elif dist == 0:
yield []
这还可以运行变成几个"dead-ends"如果还有dist
剩余,但是des
列表是空的,不过总的来说,这样会查很多比预先生成所有组合然后检查它们的距离更少的组合。
如果可能的元素列表较长,您可能需要先创建一个 dict
映射元素到它们的索引,这样您就不必每次都执行 poss.index(first)
。
示例:
possibles = [20, 30, 40, 50, 60, 70, 80, 100]
desired = [20, 30, 40]
for x in get_with_distance(possibles, desired, 2):
print(x)
输出:
[20, 20, 30]
[20, 20, 50]
[20, 30, 20]
[20, 30, 60]
[20, 40, 30]
[20, 40, 50]
[20, 50, 40]
[30, 20, 40]
[30, 30, 30]
[30, 30, 50]
[30, 40, 40]
[40, 30, 40]
我想我会展示一个可以更容易推广的更冗长的方法。
我先把问题记下来
possible_pts = [20, 30, 40, 50, 60, 70, 80, 100]
starting_pt_in_idx = [0, 1, 2]
distance = 2
有3个轴可以"change"。我首先找到轴变化的组合。
N = len(starting_pt_in_idx)
axis = list(range(N))
import itertools
axismoves = list(itertools.combinations_with_replacement(axis, distance))
print(axismoves)
接下来,我们装箱它。例如,如果我看到 axis-0 出现两次,它就会变成 [2,0,0].
abs_movements = []
for combi in axismoves:
move_bin = [0] * N
for i in combi:
move_bin[i] += 1
abs_movements.append(move_bin)
print(abs_movements)
以上给出了绝对动作。要找到实际运动,我们必须考虑沿该轴的变化可以是正的也可以是负的。
import copy
actual_movements = []
for movement in abs_movements:
actual_movements.append(movement)
for i, move in enumerate(movement):
if move != 0:
_movement = copy.deepcopy(movement)
_movement[i] = - move
actual_movements.append(_movement)
print(actual_movements)
最后一步是将索引转换为实际位置。所以首先我们写这个辅助函数。
def translate_idx_to_pos(idx_vect, points):
idx_bounds = [0, len(points) - 1]
pos_point = [0] * len(idx_vect)
for i, idx_pos in enumerate(idx_vect):
if idx_pos < idx_bounds[0] or idx_pos > idx_bounds[1]:
return None
else:
pos_point[i] = points[idx_pos]
return pos_point
使用实际运动作用于起始点索引,然后将其转换回位置。
from operator import add
final_pts = []
for movement in actual_movements:
final_pt_in_idx = list(map(add, starting_pt_in_idx, movement))
final_point = translate_idx_to_pos(final_pt_in_idx, possible_pts)
if final_point is not None:
final_pts.append(final_point)
print(final_pts)
这给出了
[40, 30, 40]
[30, 40, 40]
[30, 20, 40]
[30, 30, 50]
[30, 30, 30]
[20, 50, 40]
[20, 40, 50]
[20, 20, 50]
[20, 40, 30]
[20, 30, 60]
[20, 30, 20]
我有一个可能性列表和一个期望的输入:
possibles = [20, 30, 40, 50, 60, 70, 80, 100]
desired = [20, 30, 40]
我想生成收盘价列表。示例:
# Distance of 1 (i.e. 1 element changes to a close-by)
[30, 30, 40]
[20, 40, 40]
[20, 30, 30]
[20, 30, 50]
# Distance of 2:
[40, 30, 40]
[30, 30, 50]
[30, 40, 40]
...
我当前的版本一次只改变一个元素,因此,一旦距离超过 1,我就会缺少很多组合。
def generate_close_by(possibles, desired):
for k in range(1, 4):
for i, elt in enumerate(desired):
id = possibles.index(elt)
new = desired[:]
if id < len(possibles)-k-1:
new[i] = possibles[id+k]
yield (new)
if id > k:
new[i] = possibles[id-k]
yield (new)
# Output
[30, 30, 40]
[20, 40, 40]
[20, 30, 50]
[20, 30, 30]
[40, 30, 40]
[20, 50, 40]
[20, 30, 60]
[50, 30, 40]
[20, 60, 40]
[20, 30, 70]
我很确定应该已经存在一个模块来执行这种迭代(itertools?),你能告诉我写函数吗?
谢谢。
编辑:
尝试更新...
我正在尝试生成一个与 desired 大小相同的列表,其中每个元素对应于我必须移动 desired 元素的程度。
desired = [20, 30, 40]
# Distance of 1:
distance = [1, 0, 0]
distance = [0, 1, 0]
distance = [0, 0, 1]
distance = [-1, 0, 0]
distance = [0, -1, 0]
distance = [0, 0, -1]
然后计划尝试创建新列表,如果不能(越界),它就继续。尚未奏效,但可能是个好方法。
是的,您是对的,itertools
在这里非常有用。你想要的是找到 possibles
列表中所有具有重复项的所需长度的子集,而执行此操作的函数是 itertools.product
from itertools import product
possibles = [20, 30, 40, 50, 60, 70, 80, 100]
desired = [20, 30, 40]
def fake_hamming(cur, desired, possibles):
assert len(cur) == len(desired)
hamm = 0
for i in range(len(cur)):
assert cur[i] in possibles
assert desired[i] in possibles
hamm += abs(possibles.index(cur[i]) - possibles.index(desired[i]))
return hamm
def generate_close_by(desired, possibles, dist):
all_possible_lists = product(possibles, repeat=len(desired))
return [l for l in all_possible_lists if fake_hamming(l, desired, possibles) == dist]
print(generate_close_by(desired, possibles,1))
>>> [(20, 20, 40), (20, 30, 30), (20, 30, 50), (20, 40, 40), (30, 30, 40)]
Edit 好了,更改了产品的组合(请参阅下面的@tobias_k 评论),这里还有 fake_hamming
函数 xD
确实对于大列表来说它会很慢,但这是最通用的方法
def distribute(number, bucket):
if bucket == 1:
yield [number]
if number != 0:
yield [-1 * number]
elif number == 0:
yield [0]*bucket
else:
for i in range(number+1):
for j in distribute(number-i, 1):
for k in distribute(i, bucket-1):
yield j+k
def generate(possibles, desired, distance):
for index_distance_tuple in distribute(distance, len(desired)):
retval = desired[:]
for i, index in enumerate(index_distance_tuple):
if index + i < 0 or index + i >= len(possibles):
break
retval[i] = possibles[index + i]
else:
yield retval
对于距离 1:
for i in generate(possibles, desired, 1):
print(i)
输出:
[30, 30, 40]
[20, 40, 40]
[20, 20, 40]
[20, 30, 50]
[20, 30, 30]
对于距离 2 :
for i in generate(possibles, desired, 2):
print(i)
输出:
[40, 30, 40]
[30, 40, 40]
[30, 20, 40]
[30, 30, 50]
[30, 30, 30]
[20, 50, 40]
[20, 40, 50]
[20, 40, 30]
[20, 20, 50]
[20, 20, 30]
[20, 30, 60]
[20, 30, 20]
您可以尝试递归方法:跟踪剩余距离并仅生成相关元素的组合。
def get_with_distance(poss, des, dist, k=0):
if k < len(des):
i = poss.index(des[k])
for n in range(-dist, dist+1):
if 0 <= i + n < len(poss):
for comb in get_with_distance(poss, des, dist - abs(n), k+1):
yield [poss[i + n]] + comb
elif dist == 0:
yield []
这还可以运行变成几个"dead-ends"如果还有dist
剩余,但是des
列表是空的,不过总的来说,这样会查很多比预先生成所有组合然后检查它们的距离更少的组合。
如果可能的元素列表较长,您可能需要先创建一个 dict
映射元素到它们的索引,这样您就不必每次都执行 poss.index(first)
。
示例:
possibles = [20, 30, 40, 50, 60, 70, 80, 100]
desired = [20, 30, 40]
for x in get_with_distance(possibles, desired, 2):
print(x)
输出:
[20, 20, 30]
[20, 20, 50]
[20, 30, 20]
[20, 30, 60]
[20, 40, 30]
[20, 40, 50]
[20, 50, 40]
[30, 20, 40]
[30, 30, 30]
[30, 30, 50]
[30, 40, 40]
[40, 30, 40]
我想我会展示一个可以更容易推广的更冗长的方法。
我先把问题记下来
possible_pts = [20, 30, 40, 50, 60, 70, 80, 100]
starting_pt_in_idx = [0, 1, 2]
distance = 2
有3个轴可以"change"。我首先找到轴变化的组合。
N = len(starting_pt_in_idx)
axis = list(range(N))
import itertools
axismoves = list(itertools.combinations_with_replacement(axis, distance))
print(axismoves)
接下来,我们装箱它。例如,如果我看到 axis-0 出现两次,它就会变成 [2,0,0].
abs_movements = []
for combi in axismoves:
move_bin = [0] * N
for i in combi:
move_bin[i] += 1
abs_movements.append(move_bin)
print(abs_movements)
以上给出了绝对动作。要找到实际运动,我们必须考虑沿该轴的变化可以是正的也可以是负的。
import copy
actual_movements = []
for movement in abs_movements:
actual_movements.append(movement)
for i, move in enumerate(movement):
if move != 0:
_movement = copy.deepcopy(movement)
_movement[i] = - move
actual_movements.append(_movement)
print(actual_movements)
最后一步是将索引转换为实际位置。所以首先我们写这个辅助函数。
def translate_idx_to_pos(idx_vect, points):
idx_bounds = [0, len(points) - 1]
pos_point = [0] * len(idx_vect)
for i, idx_pos in enumerate(idx_vect):
if idx_pos < idx_bounds[0] or idx_pos > idx_bounds[1]:
return None
else:
pos_point[i] = points[idx_pos]
return pos_point
使用实际运动作用于起始点索引,然后将其转换回位置。
from operator import add
final_pts = []
for movement in actual_movements:
final_pt_in_idx = list(map(add, starting_pt_in_idx, movement))
final_point = translate_idx_to_pos(final_pt_in_idx, possible_pts)
if final_point is not None:
final_pts.append(final_point)
print(final_pts)
这给出了
[40, 30, 40]
[30, 40, 40]
[30, 20, 40]
[30, 30, 50]
[30, 30, 30]
[20, 50, 40]
[20, 40, 50]
[20, 20, 50]
[20, 40, 30]
[20, 30, 60]
[20, 30, 20]