惰性生成排列

发布于 2024-07-09 19:56:14 字数 311 浏览 7 评论 0原文

我正在寻找一种算法来生成一组排列,以便我可以在 Clojure 中制作它们的惰性列表。 即我想迭代一个排列列表,其中每个排列在我请求之前不会被计算,并且所有排列不必立即存储在内存中。

或者,我正在寻找一种算法,其中给定某个集合,它将返回该集合的“下一个”排列,以这种方式,在其自己的输出上重复调用该函数将循环遍历原始集合的所有排列,一些顺序(顺序是什么并不重要)。

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

I'm looking for an algorithm to generate permutations of a set in such a way that I could make a lazy list of them in Clojure. i.e. I'd like to iterate over a list of permutations where each permutation is not calculated until I request it, and all of the permutations don't have to be stored in memory at once.

Alternatively I'm looking for an algorithm where given a certain set, it will return the "next" permutation of that set, in such a way that repeatedly calling the function on its own output will cycle through all permutations of the original set, in some order (what the order is doesn't matter).

Is there such an algorithm? Most of the permutation-generating algorithms I've seen tend to generate them all at once (usually recursively), which doesn't scale to very large sets. An implementation in Clojure (or another functional language) would be helpful but I can figure it out from pseudocode.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

酒废 2024-07-16 19:56:14

是的,有一个“下一个排列”算法,而且它也很简单。 C++ 标准模板库 (STL) 甚至有一个名为 next_permutation 的函数。

该算法实际上找到了下一个排列——字典顺序上的下一个排列。 这个想法是这样的:假设给你一个序列,比如“32541”。 下一个排列是什么?

如果你仔细想想,你会发现它是“34125”。 你的想法可能是这样的:在“32541”中,

  • 没有办法保持“32”固定并在“541”部分找到稍后的排列,因为该排列已经是 5,4 的最后一个排列,并且1——按降序排列。
  • 因此,您必须将“2”更改为更大的数字 - 事实上,更改为“541”部分中比它大的最小数字,即 4。
  • 现在,一旦您决定排列将以“ 34”,其余数字应该按升序排列,所以答案是“34125”。

该算法旨在精确地实现该推理:

  1. 找到按降序排列的最长“尾巴”。 (“541”部分。)
  2. 将尾部之前的数字(“2”)更改为尾部中比它大的最小数字(4)。
  3. 按升序对尾部进行排序。

只要前一个元素不小于当前元素,您就可以通过从末尾开始并向后移动来有效地执行 (1.)。 你可以通过将“4”与“2”交换来完成(2.),这样你就会得到“34521”。一旦你这样做了,你就可以避免对(3.)使用排序算法,因为尾部过去和现在(想想这一点)都按降序排序,因此只需颠倒

C++ 代码即可做到这一点(请查看 /usr/include/c++/4.0.0/ 中的源代码。 bits/stl_algo.h 在您的系统上,或参阅本文 ); 将其翻译成您的语言应该很简单:[如果您不熟悉 C++ 迭代器,请将“Bi DirectionIterator”读作“指针”,如果没有下一个排列,则代码将返回 false,即我们已经按降序排列。]

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

看起来每个排列可能需要 O(n) 时间,但是如果您更仔细地考虑一下,您可以证明所有排列总共需要 O(n!) 时间,所以每次排列只需 O(1) —— 常数时间。

好处是,即使你有一个包含重复元素的序列,算法也能工作:比如,“232254421”,它会发现尾部为“54421”。 ”,交换“2”和“4”(即“232454221”),反转其余部分,得到“232412245”,这是下一个排列。

Yes, there is a "next permutation" algorithm, and it's quite simple too. The C++ standard template library (STL) even has a function called next_permutation.

The algorithm actually finds the next permutation -- the lexicographically next one. The idea is this: suppose you are given a sequence, say "32541". What is the next permutation?

If you think about it, you'll see that it is "34125". And your thoughts were probably something this: In "32541",

  • there is no way to keep the "32" fixed and find a later permutation in the "541" part, because that permutation is already the last one for 5,4, and 1 -- it is sorted in decreasing order.
  • So you'll have to change the "2" to something bigger -- in fact, to the smallest number bigger than it in the "541" part, namely 4.
  • Now, once you've decided that the permutation will start as "34", the rest of the numbers should be in increasing order, so the answer is "34125".

The algorithm is to implement precisely that line of reasoning:

  1. Find the longest "tail" that is ordered in decreasing order. (The "541" part.)
  2. Change the number just before the tail (the "2") to the smallest number bigger than it in the tail (the 4).
  3. Sort the tail in increasing order.

You can do (1.) efficiently by starting at the end and going backwards as long as the previous element is not smaller than the current element. You can do (2.) by just swapping the "4" with the '2", so you'll have "34521". Once you do this, you can avoid using a sorting algorithm for (3.), because the tail was, and is still (think about this), sorted in decreasing order, so it only needs to be reversed.

The C++ code does precisely this (look at the source in /usr/include/c++/4.0.0/bits/stl_algo.h on your system, or see this article); it should be simple to translate it to your language: [Read "BidirectionalIterator" as "pointer", if you're unfamiliar with C++ iterators. The code returns false if there is no next permutation, i.e. we are already in decreasing order.]

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes O(n!) time for all permutations in total, so only O(1) -- constant time -- per permutation.

The good thing is that the algorithm works even when you have a sequence with repeated elements: with, say, "232254421", it would find the tail as "54421", swap the "2" and "4" (so "232454221"), reverse the rest, giving "232412245", which is the next permutation.

苍白女子 2024-07-16 19:56:14

假设我们正在讨论排列值的字典顺序,则可以使用两种通用方法:

  1. 将元素的一个排列转换为下一个排列(如 ShreevatsaR 发布的),或
  2. 直接计算 n< /code>th 排列,同时从 0 向上计数 n

对于那些不会说 c++ 的人(像我一样;-),方法 1 可以通过以下伪代码实现,假设数组的从零开始索引,索引为零在“左侧”(替换一些其他结构) ,例如列表,被“留作练习”;-):

1. scan the array from right-to-left (indices descending from N-1 to 0)
1.1. if the current element is less than its right-hand neighbor,
     call the current element the pivot,
     and stop scanning
1.2. if the left end is reached without finding a pivot,
     reverse the array and return
     (the permutation was the lexicographically last, so its time to start over)
2. scan the array from right-to-left again,
   to find the rightmost element larger than the pivot
   (call that one the successor)
3. swap the pivot and the successor
4. reverse the portion of the array to the right of where the pivot was found
5. return

这是一个以 CADB 的当前排列开始的示例:

1. scanning from the right finds A as the pivot in position 1
2. scanning again finds B as the successor in position 3
3. swapping pivot and successor gives CBDA
4. reversing everything following position 1 (i.e. positions 2..3) gives CBAD
5. CBAD is the next permutation after CADB

对于第二种方法(直接计算第 n 个排列),请记住有 N!N 元素的排列。 因此,如果您要排列 N 元素,则第一个 (N-1)! 排列必须从最小元素开始,即下一个 (N-1)! 排列必须从第二小的排列开始,依此类推。 这导致了以下递归方法(同样是伪代码,从 0 开始对排列和位置进行编号):

To find permutation x of array A, where A has N elements:
0. if A has one element, return it
1. set p to ( x / (N-1)! ) mod N
2. the desired permutation will be A[p] followed by
   permutation ( x mod (N-1)! )
   of the elements remaining in A after position p is removed

例如,ABCD 的第 13 个排列如下所示:

perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}
C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}
  perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}
  A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}
    perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}
    D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}
      B (because there's only one element)
    DB
  ADB
CADB

顺便说一句,元素的“删除”可以表示为布尔值的并行数组,指示哪些元素仍然可用,因此无需在每次递归调用时创建新数组。

因此,要迭代 ABCD 的排列,只需从 0 数到 23 (4!-1) 并直接计算相应的排列。

Assuming that we're talking about lexicographic order over the values being permuted, there are two general approaches that you can use:

  1. transform one permutation of the elements to the next permutation (as ShreevatsaR posted), or
  2. directly compute the nth permutation, while counting n from 0 upward.

For those (like me ;-) who don't speak c++ as natives, approach 1 can be implemented from the following pseudo-code, assuming zero-based indexing of an array with index zero on the "left" (substituting some other structure, such as a list, is "left as an exercise" ;-):

1. scan the array from right-to-left (indices descending from N-1 to 0)
1.1. if the current element is less than its right-hand neighbor,
     call the current element the pivot,
     and stop scanning
1.2. if the left end is reached without finding a pivot,
     reverse the array and return
     (the permutation was the lexicographically last, so its time to start over)
2. scan the array from right-to-left again,
   to find the rightmost element larger than the pivot
   (call that one the successor)
3. swap the pivot and the successor
4. reverse the portion of the array to the right of where the pivot was found
5. return

Here's an example starting with a current permutation of CADB:

1. scanning from the right finds A as the pivot in position 1
2. scanning again finds B as the successor in position 3
3. swapping pivot and successor gives CBDA
4. reversing everything following position 1 (i.e. positions 2..3) gives CBAD
5. CBAD is the next permutation after CADB

For the second approach (direct computation of the nth permutation), remember that there are N! permutations of N elements. Therefore, if you are permuting N elements, the first (N-1)! permutations must begin with the smallest element, the next (N-1)! permutations must begin with the second smallest, and so on. This leads to the following recursive approach (again in pseudo-code, numbering the permutations and positions from 0):

To find permutation x of array A, where A has N elements:
0. if A has one element, return it
1. set p to ( x / (N-1)! ) mod N
2. the desired permutation will be A[p] followed by
   permutation ( x mod (N-1)! )
   of the elements remaining in A after position p is removed

So, for example, the 13th permutation of ABCD is found as follows:

perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}
C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}
  perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}
  A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}
    perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}
    D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}
      B (because there's only one element)
    DB
  ADB
CADB

Incidentally, the "removal" of elements can be represented by a parallel array of booleans which indicates which elements are still available, so it is not necessary to create a new array on each recursive call.

So, to iterate across the permutations of ABCD, just count from 0 to 23 (4!-1) and directly compute the corresponding permutation.

人事已非 2024-07-16 19:56:14

您应该查看 wikipeda 上的排列文章。 此外,还有Factoradic数字的概念。

无论如何,这道数学题还是挺难的。

C#中,您可以使用迭代器,并使用yield停止排列算法。 这样做的问题是你不能来回移动,也不能使用索引

You should check the Permutations article on wikipeda. Also, there is the concept of Factoradic numbers.

Anyway, the mathematical problem is quite hard.

In C# you can use an iterator, and stop the permutation algorithm using yield. The problem with this is that you cannot go back and forth, or use an index.

美煞众生 2024-07-16 19:56:14

生成它们的排列算法的更多示例。

资料来源:http://www.ddj.com/architect/201200326

  1. 使用 Fike 算法,这是已知最快的之一。
  2. 使用词典顺序算法。
  3. 使用非字典顺序,但运行速度比项目 2.

1.


PROGRAM TestFikePerm;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write ;
WriteLn;
permcount := permcount + 1;
END;

PROCEDURE FikePerm ;
{Outputs permutations in nonlexicographic order.  This is Fike.s algorithm}
{ with tuning by J.S. Rohl.  The array marks[1..marksizn] is global.  The   }
{ procedure WriteArray is global and displays the results.  This must be}
{ evoked with FikePerm(2) in the calling procedure.}
VAR
    dn, dk, temp : INTEGER;
BEGIN
IF 
THEN BEGIN { swap the pair }
    WriteArray;
    temp :=marks[marksize];
    FOR dn :=  DOWNTO 1
    DO BEGIN
        marks[marksize] := marks[dn];
        marks [dn] := temp;
        WriteArray;
        marks[dn] := marks[marksize]
        END;
    marks[marksize] := temp;
    END {of bottom level sequence }
ELSE BEGIN
    FikePerm;
    temp := marks[k];
    FOR dk :=  DOWNTO 1
    DO BEGIN
        marks[k] := marks[dk];
        marks[dk][ := temp;
        FikePerm;
        marks[dk] := marks[k];
        END; { of loop on dk }
    marks[k] := temp;l
    END { of sequence for other levels }
END; { of FikePerm procedure }

BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii;
permcount := 0;
WriteLn ;
WrieLn;
FikePerm ; { It always starts with 2 }
WriteLn ;
ReadLn;
END.

2.


PROGRAM TestLexPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

过程 写入数组; VAR i:整数; 开始 FOR i := 1 TO 标记大小 一定要写; 永久计数 := 永久计数 + 1; 写入Ln; 结尾;

程序 LexPerm ; { 按字典顺序输出排列。 数组标记是全局的 } { 并且具有 n 或更少的标记。 过程 WriteArray () 是全局的并且 } { 显示结果。 } VAR 工作:整数: mp、hlen、i:整数; 开始 如果 然后开始 { 交换一对 } 工作 := 分数[1]; 标记[1] := 标记[2]; 标记[2] := 工作; 写数组; 结尾 其他开始 对于 mp := 降到 1 开始吧 LexPerm<>; hlen := DIV 2; FOR i := 1 TO hlen 开始{另一次交换} 工作 := 标记[i]; 标记[i] := 标记[n - i]; 标记[n - i] := 工作 结尾; 工作 := 分数[n]; { 更多交换 } 标记[n[ := 标记[mp]; 标记[mp] := 工作; 写数组; 结尾; LexPerm<> 结尾; 结尾;

开始{主要} FOR ii := 1 TO 标记大小 DO 标记[ii] := ii; 永久计数 := 1; { 起始位置是排列 } 写Ln < 起始位置:>; 写入 莱克斯佩尔姆; 写Ln < PermCount为,permcount>; 读Ln; 结尾。

3.


PROGRAM TestAllPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] of INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

过程 写入数组; VAR i:整数; 开始 FOR i := 1 TO 标记大小 一定要写; 写入Ln; 永久计数 := 永久计数 + 1; 结尾;

过程 AllPerm (n : INTEGER); { 按非字典顺序输出排列。 数组标记是 } { 全局且有 n 个或几个标记。 过程 WriteArray 是全局的并且 } { 显示结果。 } VAR 工作:整数; mp、交换温度:整数; 开始 如果 然后开始 { 交换一对 } 工作 := 分数[1]; 标记[1] := 标记[2]; 标记[2] := 工作; 写数组; 结尾 其他开始 对于 mp := 降到 1 开始吧 ALLPerm<< n-1>>; 如果> 然后交换温度:= 1 ELSE 交换温度 := mp; 工作 := 分数[n]; 标记[n] := 标记[swaptemp}; 标记[swaptemp} := 工作; 写数组; 全部烫发< n-1>; 结尾; 结尾;

开始{主要} FOR ii := 1 TO 标记大小 DO 标记[ii] := ii 永久计数:=1; 写Ln < 起始位置; >; 写入Ln; 阿尔彼姆 标记大小>; 写Ln < Perm 计数为,permcount>; 读Ln; 结尾。

More examples of permutation algorithms to generate them.

Source: http://www.ddj.com/architect/201200326

  1. Uses the Fike's Algorithm, that is the one of fastest known.
  2. Uses the Algo to the Lexographic order.
  3. Uses the nonlexographic, but runs faster than item 2.

1.


PROGRAM TestFikePerm;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write ;
WriteLn;
permcount := permcount + 1;
END;

PROCEDURE FikePerm ;
{Outputs permutations in nonlexicographic order.  This is Fike.s algorithm}
{ with tuning by J.S. Rohl.  The array marks[1..marksizn] is global.  The   }
{ procedure WriteArray is global and displays the results.  This must be}
{ evoked with FikePerm(2) in the calling procedure.}
VAR
    dn, dk, temp : INTEGER;
BEGIN
IF 
THEN BEGIN { swap the pair }
    WriteArray;
    temp :=marks[marksize];
    FOR dn :=  DOWNTO 1
    DO BEGIN
        marks[marksize] := marks[dn];
        marks [dn] := temp;
        WriteArray;
        marks[dn] := marks[marksize]
        END;
    marks[marksize] := temp;
    END {of bottom level sequence }
ELSE BEGIN
    FikePerm;
    temp := marks[k];
    FOR dk :=  DOWNTO 1
    DO BEGIN
        marks[k] := marks[dk];
        marks[dk][ := temp;
        FikePerm;
        marks[dk] := marks[k];
        END; { of loop on dk }
    marks[k] := temp;l
    END { of sequence for other levels }
END; { of FikePerm procedure }

BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii;
permcount := 0;
WriteLn ;
WrieLn;
FikePerm ; { It always starts with 2 }
WriteLn ;
ReadLn;
END.

2.


PROGRAM TestLexPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] OF INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray; VAR i : INTEGER; BEGIN FOR i := 1 TO marksize DO Write ; permcount := permcount + 1; WriteLn; END;

PROCEDURE LexPerm ; { Outputs permutations in lexicographic order. The array marks is global } { and has n or fewer marks. The procedure WriteArray () is global and } { displays the results. } VAR work : INTEGER: mp, hlen, i : INTEGER; BEGIN IF THEN BEGIN { Swap the pair } work := marks[1]; marks[1] := marks[2]; marks[2] := work; WriteArray ; END ELSE BEGIN FOR mp := DOWNTO 1 DO BEGIN LexPerm<>; hlen := DIV 2; FOR i := 1 TO hlen DO BEGIN { Another swap } work := marks[i]; marks[i] := marks[n - i]; marks[n - i] := work END; work := marks[n]; { More swapping } marks[n[ := marks[mp]; marks[mp] := work; WriteArray; END; LexPerm<> END; END;

BEGIN { Main } FOR ii := 1 TO marksize DO marks[ii] := ii; permcount := 1; { The starting position is permutation } WriteLn < Starting position: >; WriteLn LexPerm ; WriteLn < PermCount is , permcount>; ReadLn; END.

3.


PROGRAM TestAllPerms;
CONST marksize = 5;
VAR
    marks : ARRAY [1..marksize] of INTEGER;
    ii : INTEGER;
    permcount : INTEGER;

PROCEDURE WriteArray; VAR i : INTEGER; BEGIN FOR i := 1 TO marksize DO Write ; WriteLn; permcount := permcount + 1; END;

PROCEDURE AllPerm (n : INTEGER); { Outputs permutations in nonlexicographic order. The array marks is } { global and has n or few marks. The procedure WriteArray is global and } { displays the results. } VAR work : INTEGER; mp, swaptemp : INTEGER; BEGIN IF THEN BEGIN { Swap the pair } work := marks[1]; marks[1] := marks[2]; marks[2] := work; WriteArray; END ELSE BEGIN FOR mp := DOWNTO 1 DO BEGIN ALLPerm<< n - 1>>; IF > THEN swaptemp := 1 ELSE swaptemp := mp; work := marks[n]; marks[n] := marks[swaptemp}; marks[swaptemp} := work; WriteArray; AllPerm< n-1 >; END; END;

BEGIN { Main } FOR ii := 1 TO marksize DO marks[ii] := ii permcount :=1; WriteLn < Starting position; >; WriteLn; Allperm < marksize>; WriteLn < Perm count is , permcount>; ReadLn; END.

单身情人 2024-07-16 19:56:14

clojure.contrib.lazy_seqs 中的排列函数已经声称可以做到这一点。

the permutations function in clojure.contrib.lazy_seqs already claims to do just this.

风蛊 2024-07-16 19:56:14

它在 2022 年看起来很死灵,但我还是要分享它

这里 C++ 的实现 next_permutation< Java 中的 /code> 可以找到。 在 Clojure 中使用它的想法可能类似于

(println (lazy-seq (iterator-seq (NextPermutationIterator. (list 'a 'b 'c)))))

免责声明:我是该项目的作者和维护者

It looks necromantic in 2022 but I'm sharing it anyway

Here an implementation of C++ next_permutation in Java can be found. The idea of using it in Clojure might be something like

(println (lazy-seq (iterator-seq (NextPermutationIterator. (list 'a 'b 'c)))))

disclaimer: I'm the author and maintainer of the project

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文