带桶排列的算法 [英] Algorithm for Permutation with Buckets

问题描述

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

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.

这篇关于带桶排列的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！