带桶排列的算法

本文介绍了带桶排列的算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在寻找一种像这样的算法

I am looking for an algorithm which works like this

permutateBuckets([A,B,C])

并给出以下结果:

[ [[A,B,C]], [[A,B],[C]], [[A,C],[B]], [[B,C],[A]], [[A],[B,C]], [[B],[A,C]], [[C],[A,B]], [[A],[B],[C]], [[A],[C],[B]], [[B],[A],[C]], [[B],[C],[A]], [[C],[A],[B]], [[C],[B],[A]] ]

通常:

[1,2，...，n]的排列应包括1到n个包含输入值的存储桶的任何可能排列，存储桶中值的顺序无关(例如[1,2]等于[2,1])，仅包含存储桶的顺序很重要(例如[[1,2,3]与[[3]，[1,2]]不同).

The permutation for [1,2,...,n] should include any possible arrangements of 1 up to n buckets that contain the input values, order of values within buckets is not relevant (e.g. [1,2] equals [2,1]), only the order of the containing buckets matters (e.g. [[1,2],[3]] is different than [[3],[1,2]] ).

每个输入元素必须恰好在一个存储桶中才能使结果有效(例如[1,2]的输入不能给出[[1]](缺少2)或[[1,2]，[1]](1出现两次)作为输出.

Each input element has to be in exactly one bucket for a result to be valid (e.g. an input of [1,2] cannot give [[1]] (missing 2), or [[1,2],[1]] (1 appears twice) as output).

推荐答案

最简单的方法是递归:

Make [[A]] list Insert new item in all possible places - before current sublists between all sublists after current sublists into every sublist

例如，列表 [[B] [A]] 产生5个带有项C的新列表-插入C的位置是:

For example, list [[B][A]] produces 5 new lists with item C - places to insert C are:

[ [B] [A] ] ^ ^ ^ ^ ^

和三个2级列表 [[A]，[B]]，[[B]，[A]]，[[A，B]] 产生5 + 5 + 3 =13个3级列表.

and three level-2 lists [[A],[B]], [[B],[A]], [[A,B]] produce 5+5+3=13 level-3 lists.

替代方式:生成从1 ... 1到1..n的所有n个长度不变的序列，并为每个序列生成唯一的排列.这些排列的值对应于每个项目的存储桶编号.例如，122序列给出了与分布相对应的3个排列:

Alternative way: Generate all n-length nondecreasing sequences from 1...1 to 1..n and generate unique permutations for every sequence. Values on these permutations correspond to the bucket number for every item. For example, 122 sequence gives 3 permutations that corresponds to distributions:

1 2 2 [1],[2, 3] 2 1 2 [2],[1, 3] 2 2 1 [3],[1, 2]

在任何情况下，发行数量都会迅速增加(订购的贝尔编号 1、3、13、75、541、4683、47293、545835、7087261、102247563 ... )

In any case number of distributions rises very quickly (ordered Bell numbers 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563...)

在Delphi中实现迭代方法(完整的FP兼容代码位于 ideone )

Implementation of iterative approach in Delphi (full FP-compatible code at ideone)

procedure GenDistributions(N: Integer); var seq, t, i, mx: Integer; Data: array of Byte; Dist: TBytes2D; begin SetLength(Data, N); //there are n-1 places for incrementing //so 2^(n-1) possible sequences for seq := 0 to 1 shl (N - 1) - 1 do begin t := seq; mx := 0; Data[0] := mx; for i := 1 to N - 1 do begin mx := mx + (t and 1); //check for the lowest bit Data[i] := mx; t := t shr 1; end; //here Data contains nondecreasing sequence 0..mx, increment is 0 or 1 //Data[i] corresponds to the number of sublist which item i belongs to repeat Dist := nil; SetLength(Dist, mx + 1); // reset result array into [][][] state for i := 0 to N - 1 do Dist[Data[i]] := Dist[Data[i]] + [i]; //add item to calculated sublist PrintOut(Dist); until not NextPerm(Data); //generates next permutation if possible end;

现在是Python递归实现( ideone )

And now Python recursive implementation (ideone)

import copy cnt = 0 def ModifySublist(Ls, idx, value): res = copy.deepcopy(Ls) res[idx].append(value) return res def InsertSublist(Ls, idx, value): res = copy.deepcopy(Ls) res.insert(idx, [value]) return res def GenDists(AList, Level, Limit): global cnt if (Level==Limit): print( AList) cnt += 1 else: for i in range(len(AList)): GenDists(ModifySublist(AList, i, Level), Level + 1, Limit) GenDists(InsertSublist(AList, i, Level), Level + 1, Limit) GenDists(InsertSublist(AList, len(AList), Level), Level + 1, Limit) GenDists([], 0, 3) print(cnt)

@mhmnn使用自定义项作为输出在 JavaScript 中克隆了此代码.

@mhmnn cloned this code in JavaScript using custom items for output.