标签: combinatorics

如何在Python中生成列表的所有排列,与该列表中的元素类型无关？

例如:

permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

我有n个元素.为了举个例子,让我们说,7个元素,1234567.我知道有7个!=这些7个元素可能有5040个排列.

我想要一个包含两个函数的快速算法:

f(number)将0到5039之间的数字映射到唯一的排列,并且

f'(置换)将置换映射回其生成的数字.

我不关心数字和排列之间的对应关系,只要每个排列都有自己唯一的数字.

所以,举个例子,我可能会在哪里有功能

f(0) = '1234567'
f'('1234567') = 0

想到的最快的算法是枚举所有排列并在两个方向上创建查找表,这样,一旦创建表,f(0)将是O(1)并且f('1234567')将是查找字符串.然而,这是内存饥饿,特别是当n变大时.

任何人都可以提出另一种算法,它可以快速工作,没有内存缺点吗？

当我们对列表进行排序时,比如

a = [1,2,3,3,2,2,1]
sorted(a) => [1, 1, 2, 2, 2, 3, 3]

等值元素在结果列表中始终相邻.

我怎样才能完成相反的任务 - 对列表进行洗牌,使相邻的元素永远(或尽可能不相邻)相邻？

例如,对于上面的列表,可能的解决方案之一是

p = [1,3,2,3,2,1,2]

更正式地说,给定一个列表a,生成一个p最小化对的数量的排列p[i]==p[i+1].

由于列表很大,因此不能生成和过滤所有排列.

奖金问题:如何有效地生成所有这些排列？

这是我用来测试解决方案的代码:https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD:在这里选择获胜者是一个艰难的选择,因为许多人发布了很好的答案.@VincentvanderWeele,@大卫Eisenstat,@Coady,@ enrico.bacis和@srgerg提供函数完美产生的最佳可能的排列.@tobias_k和大卫也回答了红利问题(生成所有排列).大卫的其他要点是正确性证明.

来自@VincentvanderWeele的代码似乎是最快的.

我正在寻找一种算法来生成集合的排列,这样我就可以在Clojure中创建它们的惰性列表.即我想迭代一个排列列表,其中每个排列都不计算,直到我请求它,并且所有排列不必一次存储在内存中.

或者我正在寻找一种给定某个集合的算法,它将返回该集合的"下一个"排列,以这种方式在自己的输出上重复调用该函数将循环遍历原始集合的所有排列,一些订单(订单无关紧要).

有这样的算法吗？我见过的大多数排列生成算法都倾向于一次性生成它们(通常是递归的),这些算法不能扩展到非常大的集合.Clojure(或其他函数式语言)中的实现会有所帮助,但我可以从伪代码中找出它.

我知道itertools,但它似乎只能生成排列而不重复.

例如,我想为2个骰子生成所有可能的骰子.所以我需要[1,2,3,4,5,6]的大小为2的所有排列,包括重复:(1,1),(1,2),(2,1)......等等

如果可能的话,我不想从头开始实现这一点

给定2个数组Array1 = {a,b,c...n},Array2 = {10,20,15....x}如何生成所有可能的组合作为字符串a(i)b(j)c(k)n(p) 其中

1 <= i <= 10,  1 <= j <= 20 , 1 <= k <= 15,  .... 1 <= p <= x

如:

a1 b1 c1 .... n1  
a1 b1 c1..... n2  
......  
......  
a10 b20 c15 nx (last combination)

所以在所有组合的总数=元素的产品 array2 = (10 X 20 X 15 X ..X x)

类似于笛卡尔积,其中第二个数组定义第一个数组中每个元素的上限.

固定数字的示例,

    Array x =  [a,b,c]
    Array y =  [3,2,4] 

所以我们将有3*2*4 = 24种组合.结果应该是:

    a1 b1 c1  
    a1 b1 …

我希望在Haskell中生成2个列表的笛卡尔积,但我无法弄清楚如何做到这一点.笛卡尔积给出了列表元素的所有组合:

xs = [1,2,3]
ys = [4,5,6]

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

这不是一个实际的家庭作业问题,与任何此类问题无关,但解决这个问题的方式可能有助于我坚持下去.

在java库中是否有内置方法可以为任何N,R计算'N choose R'？

我刚试过第一次编程访谈,其中一个问题是编写了一个给出7位数电话号码的程序,可以打印每个号码可能代表的所有可能的字母组合.

问题的第二部分就是如果这是一个12位数的国际号码呢？这会对你的设计产生什么影响.

我没有在采访中写的代码,但我得到的印象是他对此不满意.
做这个的最好方式是什么？

我正在尝试编写一些代码来测试一堆输入参数的笛卡尔积.

我看过了itertools,但它的product功能并不完全是我想要的.是否有一个简单明显的方法来获取具有任意数量的键和每个值中的任意数量的元素的字典,然后产生具有下一个排列的字典？

输入:

options = {"number": [1,2,3], "color": ["orange","blue"] }
print list( my_product(options) )

示例输出:

[ {"number": 1, "color": "orange"},
  {"number": 1, "color": "blue"},
  {"number": 2, "color": "orange"},
  {"number": 2, "color": "blue"},
  {"number": 3, "color": "orange"},
  {"number": 3, "color": "blue"}
]