Как создать список, элементы которого находятся на фиксированном расстоянии от желаемого списка

Question

У меня есть список возможностей и желаемый вход:

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?), Не могли бы вы указать мне функцию записи?

Спасибо.

EDIT:

Обновление попыток ...

Я пытаюсь сгенерировать список того же размера, что и желаемый элемент, в котором каждый элемент соответствует тому, насколько мне нужно переместить элемент нужного значения.

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]

И тогда планировалось попытаться создать новый список, и если он не может (выходит за пределы), он просто продолжается. Пока не работает, но может быть хорошим подходом.

Answer 1

Полагаю, я покажу более сложный подход, который можно было бы легко обобщить.

Сначала я записал проблему.

possible_pts = [20, 30, 40, 50, 60, 70, 80, 100]
starting_pt_in_idx = [0, 1, 2]
distance = 2

Есть 3 оси, которые могут «меняться». Сначала я нахожу комбинации изменений оси.

N = len(starting_pt_in_idx)
axis = list(range(N))

import itertools
axismoves = list(itertools.combinations_with_replacement(axis, distance))
print(axismoves)

Далее, мы это сделаем. Например, если я вижу ось-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]

Answer 2

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]

Answer 3

Вы можете попробовать рекурсивный подход: отслеживать оставшееся расстояние и генерировать комбинации только соответствующих элементов.

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 []

Это все еще может столкнуться с несколькими "тупиками", если все еще остается 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]

Answer 4

Да, вы правы, 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)]

Редактировать Итак, вы изменили комбинации для продукта (см. @Tobias_k комментарий ниже), а также здесь есть функция fake_hamming xD Также верно, что это будет медленно для больших списков, но это самый общий способ сделать это