堆算法 - Python 中的非递归方法生成排列
Heap's Algorithm - Non Recursive Method in Python to generate permutations
我是编程新手。我正在研究堆算法,特别是非递归方法。互联网上没有太多关于该算法如何工作的解释。我从 Bernardo Sulzbach 找到了这篇文章,但他没有解释他的算法是如何工作的。几天来我一直坚持下去,尝试了一切都无法弄清楚。我在每一行之后添加了注释以使自己理解——这里发生了什么?但我仍然无法让它发挥作用。难道我做错了什么?请帮忙。
# Heap's Algorithm (Non Recursive)
# function to swap values in python
def swap(elements, i, j):
elements[i], elements[j] = elements[j], elements[i]
# function to generate permutation
def generate_permutations(elements, n):
# Passing two parameters of elements and n to function "generate_permutations".
c = [0] * n
# c is a new list and its value set to an array literal with value 0, n times.
# Example - [a] * 3 ==> ['a', 'a', 'a', 'a']
yield elements
# "yield" statement is used to define generators, while "return" statement causes a function to exit.
# "yield" replacing the return of a function to provide a result to its caller without destroying
# local variables. Unlike a function, where on each call it starts with new sets of variables, a generator
# will resume the execution where it left off.
i = 0
# i is a new variable and its value is set to 0. It can also be used to count the number of loop runs.
while i < n:
# while loop ==> while i is less than n, do following:
if c[i] < i:
# if statement ==> while i is less than n and if any element from 'c' list is less than i,
# then do following:
if i % 2 == 0:
# if statement ==> while i is less than n, and if any element in 'c' list is less than i, and
# i is an even number, then do following:
swap(elements, 0, i)
# calling swap function and passing following arguments: elements, '0' and 'i'
else:
# else, if all three conditions above are not true then do following:
swap(elements, c[i], i)
# calling swap funtions and passing following arguments: elements, an item from 'c' list and 'i'
yield elements
# ??? yield elements
c[i] += 1
# after that, increment c[i] by 1.
i = 0
# set the value of i to 0
else:
# else, if c[i] < i is not true the do the following.
c[i] = 0
# set the value of c[i] to 0
i += 1
# and increment i by 1
def permutations(elements):
return generate_permutations(elements, len(elements))
# Driver Code
# c = ?
# n = ?
# i = ?
print(permutations(['abc']))
只是清理你的代码(评论太多):
# Heap's Algorithm (Non Recursive)
# https://en.wikipedia.org/wiki/Heap%27s_algorithm
def swap(seq, i, j):
seq[i], seq[j] = seq[j], seq[i]
def generate_permutations(seq, seqLen, resLen):
c = [0] * seqLen
yield seq[:resLen]
i = 0
while i < seqLen:
if c[i] < i:
if i % 2 == 0:
swap(seq, 0, i)
else:
swap(seq, c[i], i)
yield seq[:resLen]
c[i] += 1
i = 0
else:
c[i] = 0
i += 1
def permutations(seq, resLen=None):
if not resLen: resLen = len(seq)
return generate_permutations(seq, len(seq), resLen)
for p in permutations([1,2,3]): print(p)
for p in permutations([1,2,3],2): print(p)
我是编程新手。我正在研究堆算法,特别是非递归方法。互联网上没有太多关于该算法如何工作的解释。我从 Bernardo Sulzbach 找到了这篇文章,但他没有解释他的算法是如何工作的。几天来我一直坚持下去,尝试了一切都无法弄清楚。我在每一行之后添加了注释以使自己理解——这里发生了什么?但我仍然无法让它发挥作用。难道我做错了什么?请帮忙。
# Heap's Algorithm (Non Recursive)
# function to swap values in python
def swap(elements, i, j):
elements[i], elements[j] = elements[j], elements[i]
# function to generate permutation
def generate_permutations(elements, n):
# Passing two parameters of elements and n to function "generate_permutations".
c = [0] * n
# c is a new list and its value set to an array literal with value 0, n times.
# Example - [a] * 3 ==> ['a', 'a', 'a', 'a']
yield elements
# "yield" statement is used to define generators, while "return" statement causes a function to exit.
# "yield" replacing the return of a function to provide a result to its caller without destroying
# local variables. Unlike a function, where on each call it starts with new sets of variables, a generator
# will resume the execution where it left off.
i = 0
# i is a new variable and its value is set to 0. It can also be used to count the number of loop runs.
while i < n:
# while loop ==> while i is less than n, do following:
if c[i] < i:
# if statement ==> while i is less than n and if any element from 'c' list is less than i,
# then do following:
if i % 2 == 0:
# if statement ==> while i is less than n, and if any element in 'c' list is less than i, and
# i is an even number, then do following:
swap(elements, 0, i)
# calling swap function and passing following arguments: elements, '0' and 'i'
else:
# else, if all three conditions above are not true then do following:
swap(elements, c[i], i)
# calling swap funtions and passing following arguments: elements, an item from 'c' list and 'i'
yield elements
# ??? yield elements
c[i] += 1
# after that, increment c[i] by 1.
i = 0
# set the value of i to 0
else:
# else, if c[i] < i is not true the do the following.
c[i] = 0
# set the value of c[i] to 0
i += 1
# and increment i by 1
def permutations(elements):
return generate_permutations(elements, len(elements))
# Driver Code
# c = ?
# n = ?
# i = ?
print(permutations(['abc']))
只是清理你的代码(评论太多):
# Heap's Algorithm (Non Recursive)
# https://en.wikipedia.org/wiki/Heap%27s_algorithm
def swap(seq, i, j):
seq[i], seq[j] = seq[j], seq[i]
def generate_permutations(seq, seqLen, resLen):
c = [0] * seqLen
yield seq[:resLen]
i = 0
while i < seqLen:
if c[i] < i:
if i % 2 == 0:
swap(seq, 0, i)
else:
swap(seq, c[i], i)
yield seq[:resLen]
c[i] += 1
i = 0
else:
c[i] = 0
i += 1
def permutations(seq, resLen=None):
if not resLen: resLen = len(seq)
return generate_permutations(seq, len(seq), resLen)
for p in permutations([1,2,3]): print(p)
for p in permutations([1,2,3],2): print(p)