генерация перестановки списка путем добавления элемента другого списка - PullRequest
Новая
       11

генерация перестановки списка путем добавления элемента другого списка

0 голосов
/ 06 ноября 2019

Я пытаюсь написать код на Python, который объединяет два разных списка, C и C ', для генерации возможной перестановки. У нас есть некоторые понятия, которые я перечислю ниже: 1) F - это список, который содержит шаблон (я покажу шаблон в примере). 2) N - количество элементов в каждой сгенерированной последовательности. 3) H - количество элементов, добавляемых в C из C 'для генерации последовательностей.

Например,

C = [6,6,5,4,3,2,1]

C '= [1', 2 ', 4']

H = 3

F = [6,4,5,2,1,3]

N = 10

В этом примеремы хотим получить последовательности длиной десять, добавив три элемента C 'к C. Обратите внимание, что эти три элемента также могут быть повторяющимися элементами, такими как [1,2,1]. С другой стороны, сгенерированная последовательность должна удовлетворять F. В F. есть шаблон. Под шаблоном я подразумеваю, что F [0], который является первым элементом F, 6 должен появиться перед F [1], который является вторым элементом. из F, 4, в сгенерированной последовательности. При этом мы можем использовать некоторые правила, чтобы уменьшить количество последовательностей, которые нам нужно сгенерировать. Например, мы можем принять только 6 в первой позиции, в противном случае сгенерированные последовательности не удовлетворяют F. Мы можем принять номера 6 и 4 во второй позиции, и так далее. Наконец, количество времени, которое каждый элемент появляется в C, должно быть сохранено. В качестве примера, сгенерированные последовательности должны содержать, по крайней мере, два числа 6, одно число 5, 4,3,2,1.

Чтобы было понятно, я все объясню в следующем примере:

Возможные сгенерированные последовательности путем объединения C и C '- это [6,4', 6,5,2 ', 4,1', 3,2,1], где три элемента из C ', [4', 2', 1'], добавлено в C. Как сгенерированная последовательность удовлетворяет F? Если вы начнете слева и перебираете элементы и игнорируете повторяющиеся элементы, то у нас будет [6,4,5,2,1,3], что равно F (оно удовлетворяет F). Более того, у нас есть как минимум два числа 6, одно число 5, 4,3,2,1 в этом примере. Как я уже говорил, количество элементов в C должно быть сохранено. Например, я не могу сгенерировать последовательность вроде [6,4 ', 5,2', 4,1 ', 3,2,1,1']. Действительно, последовательность удовлетворяет F.

Представленный код не учитывает C 'и H для генерации перестановки. Мой код случайным образом генерирует перестановку, повторяя каждый возможный элемент C (без объединения C и C '), используя itertools.product (C, repeat = N). Сгенерированные последовательности имеют длину 10, и они соответствуют F. Чего не хватает: 1) Рассмотрение C 'и H для генерации последовательностей 2) Сохранение правила C (количество раз, которое каждый элемент появляется в C, необходимо сохранить.) 

import itertools
from collections import deque
import collections
from itertools import product

def Generate_F_From_Lists(constrain):
  F_list=[]
  for u in constrain:
    if u in F_list:
      pass
    else:
      F_list.append(u)
  return F_list

C= [6,6,5,4,3,2,1]
N=10
Satisfied_sequences=[]
F = [6,4,5,2,1,3]
# generate the permutation sequences of size N
for p in itertools.product(C, repeat=N):
         # rules to reduce the number of generated permutation( for example in the first position only 6 is acceptable).
    for constrain in product([6] , [6],[5, 6] ,[4, 5, 6], [3, 4, 5, 6] , [2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]):
        Generated_F=Generate_F_From_Lists(constrain)
        if Generated_F==F:
            Satisfied_sequences.append(constrain)

Заранее спасибо

...