Itertools를 사용하여 내부 브레이크가있는 가변 레벨의 중첩 된 루프

Question

Python을 배우는 숙련 된 개발자.

크기 n의 목록에서 한 번에 k 개의 조합을 반복합니다. 나는 문제가()의 내 doSomethingWith 대부분의 시간은 생산성이 아니라는 것을 지금

from itertools import chain, combinations 
for subset in (combinations(range(n), k)) : 
    doSomethingWith(subset) 

사용하고 난 내가 할 수있는 한 그들 중 많은 사람을 건너 뛰고 싶습니다. 주어진 서브셋에 대해 doSomthingWith()가 실패하면 가장 오른쪽 좌표가 큰 모든 서브셋을 건너 뛸 수 있습니다. 다시 말하면 (1,3,5,8)에 대해 실패하면, 다음에 보려는 하위 집합은 (1,3,6,0)이고 (1,3,5,9), (1, 3,5,10) 등

루프 인덱스를 명시 적으로 제어해야한다는 것을 알게되었습니다. 재귀 또는 반복을 사용하여 중첩 된 for 루프의 변수 번호가 필요합니다. 코딩하기 전에 나는 인터넷 검색을하고 유망 해 보이는 this thread을 발견했다.

from itertools import product, repeat 
set = range(n) 
sets = repeat(set, k) 

for subset in list(product(*sets)) : 
    doSomethingWith(subset) 

아름답게 파이썬을하지만, 난 여전히 같은 문제가 있습니다 :

그래서 지금은있다. 제품()에 가장 깊은 루프에서 벗어날 때를 말할 방법이 없습니다. 필자가 진정으로 원하는 것은 콜백 함수를 product()에 전달하여 실행 가능하고 선택적으로 가장 안쪽의 루프에서 벗어날 수 있도록하는 것입니다.

Pythonic suggestions? 나는 변수 중첩 루프를 명시 적으로 코딩하거나 product()에서 반환을 반복하고 손으로 부분 집합을 검사해야한다. 너무 오래 된 학교 같습니다 :-)

Answer 1

이것은 흥미로운 문제입니다. 나는 당신이 원하는 것을 얻을 수있는 발전기를 사용했다. 이것은 전체 솔루션보다 더 많은 프로토 타입입니다. 정말 유용하기 위해 조정해야 할 수도 있습니다. 그리고 내가 고려하지 않은 엣지 경우가있을 수 있습니다. (우선, 지금 그것은 단지리스트와 같은 다시 반복 가능 객체에 비우면 수 있습니다 임의의 반복 가능 객체에 제대로 작동하지 않습니다.)

class SkipUp(Exception): 
    def __init__(self, numSkips): 
     self.numSkips = numSkips 
     super(SkipUp, self).__init__(numSkips) 

def breakableProduct(*sets): 
    if not sets: 
     yield [] 
     return 
    first, rest = sets[0], sets[1:] 
    for item in first: 
     subProd = breakableProduct(*rest) 
     for items in subProd: 
      try: 
       yield [item] + items 
      except SkipUp as e: 
       if e.numSkips == 0: 
        yield None 
        break 
       else: 
        e.numSkips -= 1 
        yield subProd.throw(e) 

당신은 정상 itertools.product처럼 더 많거나 적은 breakableProduct를 사용할 수 있습니다

>>> prod = breakableProduct([1, 2, 3], [11, 22, 33], [111, 222, 333]) 
... for x, y, z in prod: 
...  print(x, y, z) 
1 11 111 
1 11 222 
1 11 333 
1 22 111 
1 22 222 
# ...etc... 
3 33 222 
3 33 333 

그러나, 그것에서 값을 얻기 후에, 당신은 누구의 인수 다음 요소 당신이 건너 뛰려는 세트의 인덱스 인, SkipUp 예외를 전달하기 위해 사용 .throw을 할 수있는 경우.

>>> prod = breakableProduct([1, 2, 3], [11, 22, 33], [111, 222, 333]) 
... for x, y, z in prod: 
...  print(x, y, z) 
...  if z == 222: 
...   prod.throw(SkipUp(1)) 
1 11 111 
1 11 222 
1 22 111 
1 22 222 
1 33 111 
1 33 222 
2 11 111 
2 11 222 
2 22 111 
2 22 222 
2 33 111 
2 33 222 
3 11 111 
3 11 222 
3 22 111 
3 22 222 
3 33 111 
3 33 222 

참조 : 당신이 SkipUp(1) (색인 0 기반이기 때문에 한 두 번째 세트입니다)를 사용, 3 세트의 모든 요소를 ​​건너 두 번째 세트의 다음 요소로 이동하려는 경우 즉, 이것이 어떻게 222 다음에 가장 안쪽의 반복을 중지 시키는가, 대신에 중간 생성자의 다음 반복으로 점프한다. 당신은 가장 바깥 쪽 반복에 모든 방법을 이동하려면 다음

>>> prod = breakableProduct([1, 2, 3], [11, 22, 33], [111, 222, 333]) 
... for x, y, z in prod: 
...  print(x, y, z) 
...  if z == 222: 
...   prod.throw(SkipUp(0)) 
1 11 111 
1 11 222 
2 11 111 
2 11 222 
3 11 111 
3 11 222 

그래서 SkipUp(0) 첫 번째 반복자의 다음 "틱"에 밖으로 점프 (즉, 목록 [1, 2, 3]). SkipUp(2)에 던져 넣는 것은 아무런 효과가 없습니다. 왜냐하면 이것은 "가장 안쪽의 반복자를 건너 뛰기"를 의미 할 것이기 때문에 정규 반복이 어쨌든 할 것입니다.

product 또는 combinationsitertools과 같은 것을 사용하는이 솔루션의 장점은 해당 생성자가 모든 조합을 생성하는 것을 막을 수 없다는 것입니다. 따라서 일부 요소를 건너 뛰어도 itertools는 모든 루핑을 수행하여 원하지 않는 모든 루핑을 생성하고 이미 생성 된 후에 만 ​​폐기합니다. 반면에이 breakableProduct은 실제로 말하면 내부 루프를 빠져 나오므로 불필요한 반복을 건너 뜁니다.

Answer 2

다음은 콜백 함수를 사용하는 상당히 기본적인 반복적 인 순서 조합 제조업체입니다. BrenBarn의 솔루션만큼 다용도는 아니지만 질문에 지정된대로 제품 생성을 건너 뜁니다. seq을 전달할 때 콜백이 실패하고 False (또는 false-ish)을 반환하면 combo은 다음으로 시작하는 다른 하위 시퀀스를 생성하지 않습니다. seq[:-1]. 당신이 if not ok: i -= 1 줄을 주석으로 경우

def combo(n, k, callback): 
    a = list(range(k)) 
    ok = callback(a) 

    k -= 1 
    while True: 
     i = k 
     if not ok: i -= 1 
     while True: 
      a[i] += 1 
      if a[i] == (n + i - k): 
       i -= 1 
       if i < 0: 
        return 
      else: 
       break 
     v = a[i] + 1 
     a[i+1:] = range(v, v + k - i) 
     ok = callback(a) 

# test 

n = 8 
k = 4 

def do_something(seq): 
    s = sum(seq) 
    ok = s <= seq[-2] * 3 
    print(seq, s, ok) 
    return ok 

combo(n, k, do_something) 

출력

[0, 1, 2, 3] 6 True 
[0, 1, 2, 4] 7 False 
[0, 1, 3, 4] 8 True 
[0, 1, 3, 5] 9 True 
[0, 1, 3, 6] 10 False 
[0, 1, 4, 5] 10 True 
[0, 1, 4, 6] 11 True 
[0, 1, 4, 7] 12 True 
[0, 1, 5, 6] 12 True 
[0, 1, 5, 7] 13 True 
[0, 1, 6, 7] 14 True 
[0, 2, 3, 4] 9 True 
[0, 2, 3, 5] 10 False 
[0, 2, 4, 5] 11 True 
[0, 2, 4, 6] 12 True 
[0, 2, 4, 7] 13 False 
[0, 2, 5, 6] 13 True 
[0, 2, 5, 7] 14 True 
[0, 2, 6, 7] 15 True 
[0, 3, 4, 5] 12 True 
[0, 3, 4, 6] 13 False 
[0, 3, 5, 6] 14 True 
[0, 3, 5, 7] 15 True 
[0, 3, 6, 7] 16 True 
[0, 4, 5, 6] 15 True 
[0, 4, 5, 7] 16 False 
[0, 4, 6, 7] 17 True 
[0, 5, 6, 7] 18 True 
[1, 2, 3, 4] 10 False 
[1, 2, 4, 5] 12 True 
[1, 2, 4, 6] 13 False 
[1, 2, 5, 6] 14 True 
[1, 2, 5, 7] 15 True 
[1, 2, 6, 7] 16 True 
[1, 3, 4, 5] 13 False 
[1, 3, 5, 6] 15 True 
[1, 3, 5, 7] 16 False 
[1, 3, 6, 7] 17 True 
[1, 4, 5, 6] 16 False 
[1, 4, 6, 7] 18 True 
[1, 5, 6, 7] 19 False 
[2, 3, 4, 5] 14 False 
[2, 3, 5, 6] 16 False 
[2, 3, 6, 7] 18 True 
[2, 4, 5, 6] 17 False 
[2, 4, 6, 7] 19 False 
[2, 5, 6, 7] 20 False 
[3, 4, 5, 6] 18 False 
[3, 4, 6, 7] 20 False 
[3, 5, 6, 7] 21 False 
[4, 5, 6, 7] 22 False 

하면 모든 조합을 생성합니다.

---

이 코드는 더 쉽게 건너 뛸 수 있도록 쉽게 수정할 수 있습니다. 콜백에서 부울 반환 값을 사용하는 대신 원하는 건너 뛰기 레벨을 반환합니다. 0을 반환하면 건너 뛰지 않습니다. 1을 반환하면 위 버전 에서처럼 seq[:-1]으로 시작하는 하위 시퀀스를 건너 뜁니다. `... 생략`list` : 콜백 2를 반환하면 우리는 ((* 세트) 제품을)

이

def combo(n, k, callback): 
    a = list(range(k)) 
    skips = callback(a) 

    k -= 1 
    while True: 
     i = k - skips 
     while True: 
      a[i] += 1 
      if a[i] == (n + i - k): 
       i -= 1 
       if i < 0: 
        return 
      else: 
       break 
     v = a[i] + 1 
     a[i+1:] = range(v, v + k - i) 
     skips = callback(a)