这里是能够解决问题的代码。为了去除重复项,我注意到,如果列表的第一个位置的值大于最后一个位置的值,则它将成为重复项。我创建了一个映射来跟踪每个项目在列表中的位置,并使用该映射进行测试。此代码还不使用递归,因此它保持其内存占用量较小。此外,该列表可以是任何类型的项目,而不仅仅是数字,请参见最后两个测试用例。
class Permutation:
def __init__(self, justalist):
self._data = justalist[:]
self._len=len(self._data)
self._s=[]
self._nfact=1
self._map ={}
i=0
for elem in self._data:
self._s.append(elem)
self._map[str(elem)]=i
i+=1
self._nfact*=i
if i != 0:
self._nfact2=self._nfact//i
def __iter__(self):
for k in range(self._nfact):
for i in range(self._len):
self._s[i]=self._data[i]
s=self._s
factorial=self._nfact2
for i in range(self._len-1):
tempi = (k // factorial) % (self._len - i)
temp = s[i + tempi]
for j in range(i + tempi,i,-1):
s[j] = s[j-1]
s[i] = temp
factorial //= (self._len - (i + 1))
if self._map[str(s[0])] < self._map[str(s[-1])]:
yield s
s=[1,2]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[1,2,3]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[1,2,3,4]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[3,2,1]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=["Apple","Pear","Orange"]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[[1,4,5],"Pear",(1,6,9),Permutation([])]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
这是我的测试案例的输出结果。
_________________________
input list: [1, 2]
[1, 2]
_________________________
input list: [1, 2, 3]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
_________________________
input list: [1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 4, 1, 3]
[3, 1, 2, 4]
[3, 2, 1, 4]
_________________________
input list: [3, 2, 1]
[3, 2, 1]
[3, 1, 2]
[2, 3, 1]
_________________________
input list: ['Apple', 'Pear', 'Orange']
['Apple', 'Pear', 'Orange']
['Apple', 'Orange', 'Pear']
['Pear', 'Apple', 'Orange']
_________________________
input list: [[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)]
[[1, 4, 5], (1, 6, 9), 'Pear', <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>, 'Pear']
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, 'Pear', (1, 6, 9)]
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9), 'Pear']
['Pear', [1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
['Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)]
['Pear', (1, 6, 9), [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>]
['Pear', <__main__.Permutation object at 0x0142DEF0>, [1, 4, 5], (1, 6, 9)]
[(1, 6, 9), [1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>]
[(1, 6, 9), 'Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>]
<=
而不是<
,这样才能适用于 n=1 的特殊情况。 - Sven Marnachp[0] <= p[-1]
还是p <= p[::-1]
? - Wei Shan Lee<
关系)? - Shoval Sadde