Почему он возвращает то же количество значений времени, что и его функция рекурсии? - PullRequest
Новая
       23

Почему он возвращает то же количество значений времени, что и его функция рекурсии?

0 голосов
/ 12 мая 2018

В этой программе я создаю подмножество всех возможных наборов, и после этого я выполняю побитовую операцию ('ИЛИ', '|') для каждого набора, и после этого я добавляю их, беру мод и печатаю ответ.

Например: 

n=3(Size of array or list)
b= 2 5 5

все возможные наборы: 

[[2,5],[2,5],[5,5],[2,5,5]]
[2,5]=7, [2,5]=7, [5,5]=5, [2,5,5]=7

Добавьте все это: 7+7+5+7=26

import itertools

def subs(l):
    res=[]
    for i in range(2,len(l)+1):
        for combo in itertools.combinations(l,i):
            res.append(list(combo))
    return res

def bitwise_operation(c):
#print("List of c : ",c)
if(len(c)>1):
        bitwise=c[0]|c[1]
        #print("Before del C : ",c)
        del c[0:2]
        #print("After  del C : ",c)
        c.append(bitwise)
        #print("After append C : ",c)
        if(len(c)>1):
            bitwise_operation(c)
print(c[0])
return c[0]

n=int(input())
bit=[]
a=list(map(int,input().split()))
b=[]
if len(a)!=n:
    exit()
else:
b=subs(a)
#print(b)
for j in range(len(b)):
    for k in range(len(b[j])-1):
        if len(b[j])>1:
            bitwise=bitwise_operation(b[j])
        #print(bitwise)
        bit.append(bitwise)
prev_ans=sum(bit)
ans=prev_ans%1000000007
print(ans)

Проблема в том, что когда я выполняю побитовую операцию с использованием рекурсивного function(bitwise_operation) [2,5,5]=[2,5]->7,[7,5]->7.........., возвращаемое значение для этого равно [2,5,5]=7

Возвращает 7, 7 дважды в одном наборе.

Как я могу это исправить?

1 Ответ

0 голосов
/ 12 мая 2018

Ваша проблема здесь. Вы добавляете результат для b[3] (элемент [2, 5, 5]) дважды. 

for j in range(len(b)):
    for k in range(len(b[j])-1):  
        if len(b[j])>1:
            bitwise=bitwise_operation(b[j])
        #print(bitwise)
        bit.append(bitwise)

Это очень сложный способ сделать простую вещь. Я поменяю ярлык, чтобы выяснить, что вы делаете. 

for index in range(len(b)):
    element = b[index]
    for times in range(len(element)-1):  # do this one time for element of len(2) and two times for an element of len(3) 
        if len(element)>1:
            bitwise=bitwise_operation(element)  # change the value of bitwise and mutate the element
        #print(bitwise)
        bit.append(bitwise)  # append that value whether it changed or not.

Итак, когда вы запускаете ваш внешний цикл, он добавляет значение для [2, 5, 5] дважды, давая вам дополнительные 7.

Вы можете получить правильный результат, напрямую итерируя по b. 

for element in b:
    bit.append(bitwise_operation(element))

Это должно дать вам правильный ответ.

Что касается примечания, bitwise_operation можно значительно упростить, выполнив итерацию непосредственно по списку. 

def new_bitwise_operation(lst):
    answer = 0
    for element in lst:
        answer = answer | element
    return answer
...