-2

我有一个列表 B=[0,0,0,0,0,0,0,0,0] 但它可以是任何长度。

我正在尝试遍历所有可以通过迭代放置在 B 中的可能值。当满足某些条件 C 时,我想“重置”我刚刚迭代的元素并将下一个项目提高 1。有点像二进制:

000 变为 001,但是当我们增加到 002 时,条件 C 满足,因此我们将其降至 0 并增加下一列:002 变为 010,依此类推。

对不起,如果我解释得不好。

所以 B 可能从

B=[0,0,0,0,1,2,5]
to
B=[0,0,0,0,1,2,6]
to
B=[0,0,0,0,1,2,7]

等等。

但是当满足条件C时,我想以这种方式重置:

B=[0,0,0,0,1,2,96]
...attempt to increment
B=[0,0,0,0,1,2,97]
...attempt to increment
Condition C met
B=[0,0,0,0,1,3,0]

并且能够做到这一点,直到我最终在最左边的元素上达到条件 C(相当于达到 1111111 并且无法再增加它)。

为了更容易编码,假设条件 C = 所有数字的总和超过 100。

我的尝试(根据 agf 的要求):

B=[0,0,0,0,0,0,0,0]
lenB=len(B)

while sum(B)<=100: #I think I have to somehow account for having tried incrementing the far left instead
    B[lenB-1]+=1 #increment last value in B
    while sum(B)>100: #if the sum is greater than 100
        B[lenB-1]=0 #reset the far right element
        B[lenB-2]+=1 #increment the next element
        #but this is wrong because it needs to perform this check again and again
        #for every column, while also checking if B[len-1] or B[len-2] even exists

编辑:实际上我的条件 C比简单地检查Sum (B)>100 复杂得多。我只是将其用作虚拟条件,因为我可以简单地将“if sum(B)>100”替换为更复杂的条件函数。

4

6 回答 6

3

编辑:我似乎已经为一个不同的、更复杂的问题创建了一个解决方案。这是我对 agf 在评论中澄清的问题的解决方案:

def uphill(initial=None):
    """Yields a tuple of integers. On each iteration, add one to the last column
    . If True is sent then reset the column, and begin iterating the previous
    column, until the first column is matched."""
    b = initial
    column = len(initial)-1
    while True:
        if (yield tuple(b)):
            b[column] = 0
            if column > 0:
                column -= 1
                b[column] += 1
            else:
                yield None
                raise StopIteration
            yield None
        else:
            b[column] += 1

gen = uphill([1, 2, 0])
for b in gen:
    print(b)
    if sum(b) >= 4:
        gen.send(True)

给我们:

(1, 2, 0)
(1, 2, 1)
(1, 3, 0)
(2, 0, 0)
(3, 0, 0)
(4, 0, 0)

旧解决方案:

我们可以使用生成器和鲜为人知的方法创建一个非常优雅的解决方案generator.send()

def waterfall(columns):
    """Yields a tuple of integers. On each iteration, adds one to the last list
    item. The consumer can send column numbers to the waterfall during iteration
     - when this is done, the specified column is reset to 0 and the previous 
    column is incremented. When the first column is reset, the iterator ends."""
    b = [0]*columns
    while True:
        reset = (yield tuple(b))
        if not reset == None:
            while not reset == None:
                b[reset] = 0
                if reset > 0:
                    b[reset-1] +=1
                else:
                    yield None
                    raise StopIteration
                reset = (yield None)
        else:
            b[-1] += 1

gen = waterfall(3)
for b in gen:
    print(b)
    if b[2] >= 3:
        gen.send(2)
    if b[1] >= 2:
        gen.send(1)
    if b[0] >= 1:
        gen.send(0)

这给了我们:

(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(0, 0, 3)
(0, 1, 0)
(0, 1, 1)
(0, 1, 2)
(0, 1, 3)
(0, 2, 0)
(1, 0, 0)

您可以愉快地将这些条件更改为任何内容。当满足您的选择条件时,您只需向生成器发送您希望重置的列的索引(它会自动将其上方的索引加一)。当最后一列被重置时,它完成了生成器。

还值得注意的是,您可以随时使用gen.close()它来停止它,而无需到达最后一列。(gen.send(0)与 相同gen.close())。

具有不同条件的示例:

gen = waterfall(2)
for b in gen:
    print(b)
    if sum(b) >= 3:
        gen.send(1)
    if b[0] >= 3:
        gen.send(0)

给我们:

(0, 0)
(0, 1)
(0, 2)
(0, 3)
(1, 0)
(1, 1)
(1, 2)
(2, 0)
(2, 1)
(3, 0)
于 2012-04-17T19:04:45.310 回答
1
def increment(box, condition):
    # last index in the list
    maxindex = index = len(box) - 1
    while True:
        # so you can see it's correct
        print box
        # increment the last digit
        box[-1] += 1
        # while the overflow condition is True
        while condition(box):
            # reset the current digit
            box[index] = 0
            # and move to the next index left
            index -= 1
            # if we're past the end of the list
            if index < 0:
                # stop
                return
            # increment the current digit
            box[index] += 1
        # back to the rightmost digit
        index = maxindex

increment([0] * 3, lambda box: sum(box) > 4)
于 2012-04-17T18:17:17.683 回答
0

您可以通过列表理解来做到这一点,并且range()(在此处使用较小的值来阻止输出非常大):

>>> [(a, b, c) for a in range(2) for b in range(4) for c in range(3)]
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (0, 3, 0), (0, 3, 1), (0, 3, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 3, 0), (1, 3, 1), (1, 3, 2)]

请注意,如果您想循环它,而不是在开始时生成一个大列表,使用生成器表达式只会根据需要创建项目:

for a, b, c in ((a, b, c) for a in range(2) for b in range(4) for c in range(3)):
    ...

请注意,在 Python 2.x 中,您希望使用xrange()而不是range获取生成器而不是列表。

于 2012-04-17T18:13:20.170 回答
0

这是做你想做的吗?

B=[0,1,0]

def check(ll,callback):
    """
    This function only works if you 
    increment the last element in the list.
    All other incrementing is done in this function.
    """
    for idx in reversed(range(len(ll))):
        if(callback(ll)):
            ll[idx]=0
            ll[idx-1]+=1
        else:
            break  #this index wasn't updated, so the next one won't be either.

    #a check to see if every element is 1
    return all(map(lambda x: x==1,ll))

def checksum(ll):
    return True if sum(ll)>100 else False

count=0
while True:
    count+=1
    B[-1]+=1
    if(check(B,checksum)): break
    print B

print B   # [1,1,1]
print count

即使对于这个例子,我们在 [1,1,1] 之前运行了超过 5000 次迭代

编辑

添加了一个简单的break语句,因为只需要检查列表,只要它在最后一次迭代期间发生了变化。

于 2012-04-17T18:23:36.690 回答
0

紧凑但低效的解决方案

如果您的条件不是特定于数字的,请尝试使用类似于 LattyWare 的解决方案,但使用过滤器仅提供预测结果。

如果您有一个谓词函数列表映射(a, b, c)bool

for a, b, c in ((a, b, c) for a in range(2) for b in range(4) for c in range(3)):
    if all [p(a,b,c) for p in predicates]:
        yield a, b, c

请注意,如果您不能对各个数字设置合理的初始界限(搜索空间变得太大),这将变得站不住脚。

于 2012-04-17T18:28:45.140 回答
0

正如您所期望的那样,这似乎解决了您不断增加的问题:

b=[0,0,0,0,0,0,0,1,7]

def incr(arr, condition, pred):
   arr[-1] += 1
   element = -1
   while condition(arr) > pred:

      if arr[element]:
         arr[element] = 0
         arr[element-1] += 1
      else:
         element -= 1
      if abs(element) == len(arr):
         break
   return arr

print b
for i in xrange(0,10):
   b = incr(b, sum, 15)
   print b

函数接受列表和函数条件(例如,总和)以及增量应该结转的点。

因此,对于示例 sum (15),它会返回如下结果:

>>> 
[0, 0, 0, 0, 0, 0, 0, 1, 7]
[0, 0, 0, 0, 0, 0, 0, 1, 8]
[0, 0, 0, 0, 0, 0, 0, 1, 9]
[0, 0, 0, 0, 0, 0, 0, 1, 10]
[0, 0, 0, 0, 0, 0, 0, 1, 11]
[0, 0, 0, 0, 0, 0, 0, 1, 12]
[0, 0, 0, 0, 0, 0, 0, 1, 13]
[0, 0, 0, 0, 0, 0, 0, 1, 14]
[0, 0, 0, 0, 0, 0, 0, 2, 0]
[0, 0, 0, 0, 0, 0, 0, 2, 1]
[0, 0, 0, 0, 0, 0, 0, 2, 2]
于 2012-04-17T18:33:37.370 回答