如何在Perl中生成长度为k的所有有序组合？ [英] How can I generate all ordered combinations of length k in Perl?

问题描述

我需要一个给定字符集的子例程，该子例程将生成长度为k的那些字符的所有可能组合。订单很重要，并且允许重复使用，因此如果 k = 2 ，则 AB！= BA 和 AA 是一个选项。我在PerlMonks上找到了一些可用的示例，但不幸的是，它们是代码高尔夫，对我而言并不容易包缠我的思想。有人可以做下面的一个或多个吗？

I need a subroutine that, given a set of characters, will generate all possible combinations of those characters of length k. Order matters and reuse is allowed, so if k = 2 then AB != BA and AA is an option. I found some working examples on PerlMonks, but unfortunately they are code golf and not easy for me to wrap my mind around. Can someone please do one or more of the following?

1. 给出第一个算法的分解和解释。


2. 对代码进行模糊处理，以使含义更清楚。


3. 将我引向另一个更清晰的示例。

谢谢！

推荐答案

您可以使用 variations_with_repetition = nofollow> Algorithm :: Combinatorics （它还提供了基于迭代器的接口），但是如果您只需要一个列表，这是一个相当简单的递归算法：

You can use variations_with_repetition from Algorithm::Combinatorics (which also provides an iterator-based interface), but if you just need a list, this is a fairly simple recursive algorithm:

sub ordered_combinations
{
  my ($data, $k) = @_;

  return @$data if $k == 1;

  my @previous = ordered_combinations($data, $k-1);

  my @results;
  for my $letter (@$data) {
    push @results, map { $letter . $_ } @previous;
  }

  return @results;
} # end ordered_combinations

print "$_\n" for ordered_combinations([qw(a b c)], 3);

这基本上与高尔夫球手使用的算法相同，但是我使用的是 for 循环而不是嵌套 map 。另外，我每个级别仅递归一次（代码高尔夫是关于最小化源代码，而不是运行时）。

This is basically the same algorithm the code golfers are using, but I'm using a for loop instead of nesting map. Also, I recurse only once per level (code golf is about minimizing source code, not runtime).

任何递归函数都可以转换为迭代函数，这通常会减少它的开销。这很简单：

Any recursive function can be converted to an iterative one, which usually reduces its overhead. This one is fairly simple:

sub ordered_combinations
{
  my ($data, $k) = @_;

  return if $k < 1;

  my $results = $data;

  while (--$k) {
    my @new;
    for my $letter (@$data) {
      push @new, map { $letter . $_ } @$results;
    } # end for $letter in @$data

    $results = \@new;
  } # end while --$k is not 0

  return @$results;
} # end ordered_combinations

此版本处理 $ k = = 0 情况，原始情况没有。

This version handles the $k == 0 case, which the original did not.

这篇关于如何在Perl中生成长度为k的所有有序组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！