在Python或Cpp中没有前导或尾随0的1的排列

问题描述 投票:0回答:1

我需要一种有效的方法来生成探索Nx1和Kx0的所有排列的列表列表。但是,我需要删除所有前导和尾随0,然后删除重复项。 K-N将在100年代,N将在2到20之间。

我可以在以下步骤中执行此操作:1)创建排列2)删除每个列表元素的尾随0 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]]
python math iteration permutation combinatorics
1个回答
1
投票

在Engineero的评论中回答。

删除前导和尾随0与说它需要以1开始和结束相同。因此,用N-2进行排列,然后在末端绑上1。

谢谢!

编辑:我认为Engineero回答了这个问题,但实际上他并没有解决当第一个和最后一个之间的距离小于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);
© www.soinside.com 2019 - 2024. All rights reserved.