Вот код, который делает трюк. Чтобы избавиться от дубликатов, я заметил, что для вашего списка, если значение первого местоположения больше, чем значение последнего местоположения, то это будет дублирование. Я создаю карту, чтобы отслеживать, где каждый элемент находился в списке для начала, а затем использую эту карту для проведения теста. Код также не использует рекурсию, поэтому он сохраняет небольшой объем памяти. Также в списке могут быть элементы любого типа, а не только цифры, см. Последние два теста.
Вот код.
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>]