Блог

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

Для этого я запускаю рекурсивную функцию, которая работает, но мне нужно создать список с результатами.

 # Function to print all n–digit binary strings without any consecutive 0's
def countStrings(n, out="", last_digit=0):
    # if the number becomes n–digit, print it
    
    if n == 0:
        print(out)
        return
    
    # append 0 to the result and recur with one less digit
    countStrings(n - 1, out   '1', 0)
    
 
    # append 1 to the result and recur with one less digit
    # only if the last digit is 0
    if last_digit == 0:
        countStrings(n - 1, out   '0', 1)
 

Когда я запускаю его, например: a = countStrings(3) , он печатает все возможные варианты, но переменная «a» возвращается как «None»:

Результаты:

 111
110
101
011
010

type(a): Nonetype
 

Я пытался вставить добавление в некоторых местах, но безрезультатно

Я понятия не имею, чего мне не хватает

Это то, что вы ищете?

 # Function to print all n–digit binary strings without any consecutive 0's
def countStrings(n, out="", last_digit=0, acc=[]):
    # if the number becomes n–digit, print it
    
    if n == 0:
        print(out)
        acc.append(out)
        return acc
    
    # append 0 to the result and recur with one less digit
    countStrings(n - 1, out   '1', 0, acc)
    
 
    # append 1 to the result and recur with one less digit
    # only if the last digit is 0
    if last_digit == 0:
        countStrings(n - 1, out   '0', 1, acc)
    return acc

acc = countStrings(3)
print('acc', acc)
 

Вывод:

 111
110
101
011
010
('acc', ['111', '110', '101', '011', '010'])
 

Если вы не хотите использовать return , вы можете создать global параметр и вызвать его, как только функция завершит выполнение:

 res = []

def countStrings(n, out="", last_digit=0):
    global res
    # if the number becomes n–digit, print it
    if n == 0:
        print(out)
        res.append(out)
        return 
    
    # append 0 to the result and recur with one less digit
    countStrings(n - 1, out   '1', 0)
    
 
    # append 1 to the result and recur with one less digit
    # only if the last digit is 0
    if last_digit == 0:
        countStrings(n - 1, out   '0', 1)
 

Вызов print(res) даст вам:

 ['111', '110', '101', '011', '010']
 

решение A

Я бы предложил разделить задачи программы на несколько функций —

 def binaries(n):
  for m in range(2 ** n):
    yield f"{m:>0{n}b}"
 

 print(list(binaries(3)))
 

 ['000', '001', '010', '011', '100', '101', '110', '111']
 

Теперь мы можем написать pairwise , который выполняет попарную итерацию по итерируемому —

 from itertools import tee, islice

def pairwise(t):
  a, b = tee(t)
  yield from zip(a, islice(b, 1, None))
 

 print(list(pairwise("011001")))
 

 [('0', '1'), ('1', '1'), ('1', '0'), ('0', '0'), ('0', '1')]
 

Теперь это легко реализовать solution как комбинацию всех binaries размеров n , где pairwise анализ любого конкретного двоичного файла не содержит двух соседних нулей —

 def solution(n):
  for b in binaries(n):
    for p in pairwise(b):
      if p == ('0','0'):
        break
    else:
      yield b
 

 print(list(solution(3)))
 

 ['010', '011', '101', '110', '111']
 

Если всем нужно только количество решений, мы можем написать count_solutions как специализацию solutions —

 def count_solutions(n):
  return len(list(solution(n)))
 

 print(count_solutions(3))
 

 5
 

Давайте посмотрим, как это работает на более крупном примере, n = 8 —

 print(list(solutions(8)))
print(count_solutions(8))
 

 ['01010101', '01010110', '01010111', '01011010', '01011011', '01011101', '01011110', '01011111', '01101010', '01101011', '01101101', '01101110', '01101111', '01110101', '01110110', '01110111', '01111010', '01111011', '01111101', '01111110', '01111111', '10101010', '10101011', '10101101', '10101110', '10101111', '10110101', '10110110', '10110111', '10111010', '10111011', '10111101', '10111110', '10111111', '11010101', '11010110', '11010111', '11011010', '11011011', '11011101', '11011110', '11011111', '11101010', '11101011', '11101101', '11101110', '11101111', '11110101', '11110110', '11110111', '11111010', '11111011', '11111101', '11111110', '11111111']
55
 

решение B

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

Сначала мы пишем bitwise —

 def bitwise(n, e):
  if e == 0:
    return
  else:
    yield from bitwise(n >> 1, e - 1)
    yield n amp; 1
 

 for n in range(2 ** 3):
  print(tuple(bitwise(n, 3)))
 

 (0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
 

Затем pairwise —

 from itertools import tee, islice

def pairwise(t):
  a, b = tee(t)
  yield from zip(a, islice(b, 1, None))
 

 for n in range(2 ** 3):
  print(bin(n), list(pairwise(bitwise(n, 3))))
 

 0b0 [(0, 0), (0, 0)]
0b1 [(0, 0), (0, 1)]
0b10 [(0, 1), (1, 0)]
0b11 [(0, 1), (1, 1)]
0b100 [(1, 0), (0, 0)]
0b101 [(1, 0), (0, 1)]
0b110 [(1, 1), (1, 0)]
0b111 [(1, 1), (1, 1)]
 

Наконец solution —

 def solution(e):
  for n in range(2 ** e):
    for p in pairwise(bitwise(n, e)):
      if p == (0, 0):
        break
    else:
      yield n
 

 sln = list(map(bin, solution(3)))
print(sln)
print(len(sln))
 

 ['0b10', '0b11', '0b101', '0b110', '0b111']
5
 

И n = 8 —

 sln = list(map(bin, solution(8)))
print(sln)
print(len(sln))
 

 ['0b1010101', '0b1010110', '0b1010111', '0b1011010', '0b1011011', '0b1011101', '0b1011110', '0b1011111', '0b1101010', '0b1101011', '0b1101101', '0b1101110', '0b1101111', '0b1110101', '0b1110110', '0b1110111', '0b1111010', '0b1111011', '0b1111101', '0b1111110', '0b1111111', '0b10101010', '0b10101011', '0b10101101', '0b10101110', '0b10101111', '0b10110101', '0b10110110', '0b10110111', '0b10111010', '0b10111011', '0b10111101', '0b10111110', '0b10111111', '0b11010101', '0b11010110', '0b11010111', '0b11011010', '0b11011011', '0b11011101', '0b11011110', '0b11011111', '0b11101010', '0b11101011', '0b11101101', '0b11101110', '0b11101111', '0b11110101', '0b11110110', '0b11110111', '0b11111010', '0b11111011', '0b11111101', '0b11111110', '0b11111111']
55
 

рекомендуемое чтение

Если вы никогда не видели for..else цикл в Python, пожалуйста, прочитайте документы об этой замечательной конструкции