普遍认为n个不同符号的列表有n!排列.然而,当符号不明显时,在数学和其他地方最常见的惯例似乎只计算不同的排列.因此,列表的排列[1, 1, 2]通常被认为是
[1, 1, 2], [1, 2, 1], [2, 1, 1].实际上,以下C++代码正好打印出这三个:
int a[] = {1, 1, 2};
do {
cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
} while(next_permutation(a,a+3));
另一方面,Python itertools.permutations似乎打印其他东西:
import itertools
for a in itertools.permutations([1, 1, 2]):
print a
这打印
(1, 1, 2)
(1, 2, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 1, 1)
正如用户Artsiom Rudzenka在一个答案中指出的那样,Python文档说:
元素根据其位置而不是其价值被视为唯一元素.
我的问题:为什么做出这个设计决定？
似乎遵循通常的惯例会给出更有用的结果(事实上它通常正是我想要的)......或者是否存在一些我缺少的Python行为应用？
[或者是一些实施问题？这里的算法next_permutation- 例如在StackOverflow上解释(由我)并在这里显示为O(1)摊销 - 在Python中似乎是高效和可实现的,但是Python做了更有效的事情,因为它不保证基于词典顺序价值？如果是这样,效率的提高是否值得呢？]
问题是打印两个给定字符串的所有可能的交错.所以我用Python编写了一个工作代码,运行方式如下:
def inter(arr1,arr2,p1,p2,arr):
thisarr = copy(arr)
if p1 == len(arr1) and p2 == len(arr2):
printarr(thisarr)
elif p1 == len(arr1):
thisarr.extend(arr2[p2:])
printarr(thisarr)
elif p2 == len(arr2):
thisarr.extend(arr1[p1:])
printarr(thisarr)
else:
thisarr.append(arr1[p1])
inter(arr1,arr2,p1+1,p2,thisarr)
del thisarr[-1]
thisarr.append(arr2[p2])
inter(arr1,arr2,p1,p2+1,thisarr)
return
它出现在字符串中的每个点上,然后对于一个递归调用,它将当前元素视为属于第一个数组,并在下一个调用中将其视为属于另一个数组.因此,如果输入的字符串ab和cd,它打印出来abcd,acbd,cdab,cabd,等p1,并p2都指向数组(因为Python中的字符串是不可改变的,我使用数组!).任何人都可以告诉我,这段代码的复杂程度是什么,是否可以改进？我编写了一个类似的代码来打印k给定数组的所有长度组合:
def kcomb(arr,i,thisarr,k):
thisarr = copy(thisarr)
j,n = len(thisarr),len(arr)
if n-i<k-j or j >k:
return
if j==k:
printarr(thisarr)
return
if i == n:
return
thisarr.append(arr[i])
kcomb(arr,i+1,thisarr,k)
del …我想知道next_permutation函数的时间复杂度.我也可以查看它的代码吗？
问题是：给定一组可能包含重复项的数字，返回所有唯一的排列。
天真的方法是使用一个集合（在 C++ 中）来保存排列。这需要O ( n ! × log( n !)) 时间。有更好的解决方案吗？