what I expect for [1,2,3] ->

[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

but my function give this result, I can not fix it ->

def foo(L,first,last,Output):
    if first>=last:
        return
    for i in range(first ,last):
        print(Output [L[i]])
        foo(L,first 1,last,Output [L[i]])
        


foo([1,2,3],0,3,[])


[1]
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 3]
[2]
[2, 2]
[2, 2, 3]
[2, 3]
[2, 3, 3]
[3]
[3, 2]
[3, 2, 3]
[3, 3]
[3, 3, 3]

and in some situation I want to stop calculation and continue with others:

let say if 1 and 2 get come together , dont continue anymore

-> for [1,2,3] and (1,2)

what I expect :

[1]
[1, 3]
[2]
[2, 3]
[3]

iterative function is also good for me

CodePudding user response：

inductive reasoning

Another way to think about the problem doesn't involve ranges, indexes or incrementing them, leading to many off-by-one errors. Instead we can reason about the problem inductively -

1. If the input t is empty, yield the empty set
2. (inductive) t has at least one element. For all p in the recursive sub-problem powerset(t[1:]), yield p and yield p with the first element, t[0] prepended.

def powerset(t):
  if not t:
    yield ()                       # 1. empty t
  else:
    for p in powerset(t[1:]):      # 2. at least one element
      yield p
      yield (t[0], *p)

By using yield we move the desired effect outside of the powerset function. This allows the caller to decide what happens with each produced set -

for p in powerset("abc"):
  print(p)                   # <- desired effect

()
('a',)
('b',)
('a', 'b')
('c',)
('a', 'c')
('b', 'c')
('a', 'b', 'c')

for p in powerset("abc"):
  print("".join(p))     # <- different effect

a
b
ab
c
ac
bc
abc

changing the order

I just want to process sequentially as I showed in the example.

The particular order you asked for can be achieved by reordering the yields. I also made an adjustment to remove the empty set from the output -

1. if the input t is empty, stop
2. (inductive) t has at least one element
   • yield the singleton set of the first element, t[0]
   • prepend the first element to each result of the sub-problem powerset(t[1:]) and yield
   • yield each result of the sub-problem powerset(t[1:])

def powerset(t):
  if not t:
    return                 # 1.
  else:
    yield (t[0],)          # 2.
    yield from map(lambda p: (t[0], *p), powerset(t[1:]))
    yield from powerset(t[1:])

Notice above we compute powerset(t[1:]) twice. This is wasteful and can be avoided using itertools.tee -

from itertools import tee

def powerset(t):
  if not t: return
  yield (t[0],)
  left, right = tee(powerset(t[1:]))          # <- tee left & right
  yield from map(lambda p: (t[0], *p), left)  # <- left
  yield from right                            # <- right

for p in powerset("abc"):
  print(p)

('a',)
('a', 'b')
('a', 'b', 'c')
('a', 'c')
('b',)
('b', 'c')
('c',)

list of all subsets

Is it possible to do it without using yield? I need to keep it in a global list

Python uses iterables throughout its standard library. The prescribed way is to use yield however it's easy to convert to list using list -

result = list(powerset("abc"))
print(result)

[('a',), ('a', 'b'), ('a', 'b', 'c'), ('a', 'c'), ('b',), ('b', 'c'), ('c',)]

without using yield

If you have some compelling reason where powerset must return an array instead of an iterable, the transformation is elementary. Notice the structure of the program is identical -

def powerset(t):
  if not t: return []
  result = list(powerset(t[1:]))
  return [
    (t[0],),
    *map(lambda p: (t[0], *p), result),
    *result
  ]

print(powerset("abc"))

[('a',), ('a', 'b'), ('a', 'b', 'c'), ('a', 'c'), ('b',), ('b', 'c'), ('c',)]

CodePudding user response：

def helper(L,first,last,Output,isBack):
    if first>=last-1:
        return
    
    for i in range(first ,last):
        if L[i] in Output:
            continue
        print(Output [L[i]])
        
        if isBack:
            helper(L,first i,last,Output [L[i]],False)
            
        else:
            helper(L,first 1,last,Output [L[i]],False)
            
        isBack=True

def powerset(L):
    helper(L,0,len(L),[],True)

powerset([1,2,3,4,5])

Output:

[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 5]
[1, 2, 4]
[1, 2, 5]
[1, 3]
[1, 3, 5]
[1, 4]
[1, 5]
[2]
[2, 3]
[2, 3, 4]
[2, 3, 4, 5]
[2, 3, 5]
[2, 4]
[2, 5]
[3]
[3, 4]
[3, 4, 5]
[3, 5]
[4]
[4, 5]
[5]

it could be better but that's all I could do