这是一个创建于 1668 天前的主题，其中的信息可能已经有所发展或是发生改变。
菜鸟写了一个排列组合算法，不用递归;主要不用到交换；主要是利用 数组的补集数组的最值。
组合数添加：文档
假设为 C(n, m)模式。当前列表为 @list，初始值为[1,2,..m]，有 m 个元素。
@model 是 1~n 所有整数构成的数组
delta 数组是 @model 减去 @list 的所有元素。
...@list 从后往前找到第一个元素 A，其位置为 ji，使得 A<delta 数组内的最大值 B(应该是 delta 数组的最后一位)
...若存在 B，则找出 delta 数组内所有比 A 大的元素集合中的最小值 C 。
...把 @list 的 ji 位置替换为 C 元素。
...对于更新后的 @list 从位置 0 到 ji 的子集 D，获取 @model-D 的数组中所有大于 C 的元素组成的集合 E 。
......如果 E 为空，则 @list 从 ji 到(m-1)位置上所有的数是 n 、n-1 、n-2 ...，此时 @list 符合条件。直接跳出流程
......如果 E 不为空，则把 @list 从(ji+1)到(m-1)位置，依次设为 E[0]、E[1]..。
......若不存在 B， 则继续从后往前找到对应的元素 A
...如果整个 @list 都找不到符合条件的 A，则 @list 已是本次组合中的最大倒序排列: [n, n-1, n-2 ...]。直接跳出流程
情景是用老方法生成 8 nPr 8 时，已经有 4 万个集合了，如果 n 和 m 再大一点，ruby 肯定要爆内存了。于是想借用 ruby 的迭代器来实现循环；于是就要根据当前的排列数组生成下一步的排列数组，（组合数组的操作同理）。
看了一下百度前几页，要么递归，要么交换。递归这个因为 ruby 性能问题所以我不能用，交换这个我想了一下，感觉没我现在这个算法写着舒服。
现在这个算法不占内存，但是速度比较着急，用 ruby-prof 看出来是在 获取当前排列数组的补集数组 的循环里面较慢；暂时没想到怎么解决。
至于把这个类转化成 ruby 迭代器，一时忘记 Enumerable 和.each()是要怎么写的了，还要再搜一下代码，哈哈。
菜鸟一枚，求轻拍。地址是 https://gitee.com/crella/sanla/blob/master/permlist.rb
组合数添加：文档
假设为 C(n, m)模式。当前列表为 @list，初始值为[1,2,..m]，有 m 个元素。
@model 是 1~n 所有整数构成的数组
delta 数组是 @model 减去 @list 的所有元素。
...@list 从后往前找到第一个元素 A，其位置为 ji，使得 A<delta 数组内的最大值 B(应该是 delta 数组的最后一位)
...若存在 B，则找出 delta 数组内所有比 A 大的元素集合中的最小值 C 。
...把 @list 的 ji 位置替换为 C 元素。
...对于更新后的 @list 从位置 0 到 ji 的子集 D，获取 @model-D 的数组中所有大于 C 的元素组成的集合 E 。
......如果 E 为空，则 @list 从 ji 到(m-1)位置上所有的数是 n 、n-1 、n-2 ...，此时 @list 符合条件。直接跳出流程
......如果 E 不为空，则把 @list 从(ji+1)到(m-1)位置，依次设为 E[0]、E[1]..。
......若不存在 B， 则继续从后往前找到对应的元素 A
...如果整个 @list 都找不到符合条件的 A，则 @list 已是本次组合中的最大倒序排列: [n, n-1, n-2 ...]。直接跳出流程
情景是用老方法生成 8 nPr 8 时，已经有 4 万个集合了，如果 n 和 m 再大一点，ruby 肯定要爆内存了。于是想借用 ruby 的迭代器来实现循环；于是就要根据当前的排列数组生成下一步的排列数组，（组合数组的操作同理）。
看了一下百度前几页，要么递归，要么交换。递归这个因为 ruby 性能问题所以我不能用，交换这个我想了一下，感觉没我现在这个算法写着舒服。
现在这个算法不占内存，但是速度比较着急，用 ruby-prof 看出来是在 获取当前排列数组的补集数组 的循环里面较慢；暂时没想到怎么解决。
至于把这个类转化成 ruby 迭代器，一时忘记 Enumerable 和.each()是要怎么写的了，还要再搜一下代码，哈哈。
菜鸟一枚，求轻拍。地址是 https://gitee.com/crella/sanla/blob/master/permlist.rb
 |
1
crella OP 使用方法见同一仓库下的 list-test.rb
|
Select Language