Перестановки 1 с без начальных или конечных 0 в Python или Cpp - PullRequest
Новая
       42

Перестановки 1 с без начальных или конечных 0 в Python или Cpp

0 голосов
/ 05 марта 2019

Мне нужен эффективный способ создания списка списков, исследующих все перестановки Nx1s и Kx0s. Однако мне нужно удалить все начальные и конечные 0, а затем удалить дубликаты. K-N будет в сотнях, N будет где-то между 2 и 20.

Я могу сделать это по шагам: 1) Создание перестановок 2) Удалить завершающие нули для каждого элемента списка 3) Удалить ведущие 0 для каждого элемента списка 4) Удалить дубликаты

Однако первые 3 шага занимают очень много времени, поэтому я думаю, что мне нужно найти другой подход. Вот код, который я использовал: 

import itertools

def donewk(k):
  newk = []
  for i in k:
    if i not in newk:
      newk.append(i)
  return newk

n=2;
k=10;
a=(list(itertools.permutations( [1]*n+[0]*(k-2))))
for i,elem in enumerate(a):
    elem = list(elem)
    while not elem[-1]:
        elem.pop()
    while not elem[0]:
        elem.pop(0)
    a[i]=elem;

a=donewk(a)
print(a)

выход 

[[1, 1], [1, 0, 1], [1, 0, 0, 1], [1, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1]]

1 Ответ

1 голос
/ 05 марта 2019

Ответил в комментариях Engineero.

Удаление начальных и конечных нулей - это то же самое, что сказать, что нужно начинать и заканчивать единицами. Для этого возьмите перестановку с N-2 и затем закрепите 1 на концах.

Спасибо!

EDIT: Я думал, что Engineero ответил на вопрос, но на самом деле он не сделал, так как это не решает проблему, когда расстояние между первым и последним 1 меньше, чем K. Он действительно дал удовлетворительный ответ.

Я создал итеративное приложение. Мое последнее приложение - cpp, но я сделал быстрый прототип на python в качестве доказательства концепции. Заметьте, что в приложении cpp вместо добавления в мой список я буду вызывать отдельную функцию, которая использует перестановку. Не стесняйтесь критиковать, чтобы сделать его более эффективным. 

import copy
aList = []

def initA(sz=10):
        return [1]+[0]*(sz-2)+[1];

def iterA(buff,level,ix):
    if (level >0):
        for i in range (level,ix):
            a=copy.deepcopy(buff)
            a[i] = 1;
            if level ==1:
                aList.append(a)
            iterA(a,level-1,i);

N=6;
K=10;
for i in range (N-2,K):
    a=initA(i+1)
    a = iterA(a,N-2,i)
print (aList);
...