Как я могу сгенерировать все упорядоченные комбинации длины k в Perl?

Вы можете использовать variations_with_repetition из Algorithm::Combinatorics (который также предоставляет интерфейс на основе итератора), но если вам просто нужен список, это довольно простой рекурсивный алгоритм:

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. Кроме того, я рекурсивно выполняю только один раз на уровне (код-гольф касается минимизации исходного кода, а не времени выполнения).

Любую рекурсивную функцию можно преобразовать в итеративную, что обычно снижает ее накладные расходы. Это довольно просто:

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, чего не было в оригинале.

Я взглянул на самый первый фрагмент кода на странице, на которую вы ссылались:

sub c{my$n=-1+shift;$n?map{my$c=$_;map$c.$_,c($n,@_)}@_:@_}

Я немного расширил его, чтобы сделать его более читабельным; также я внес в него некоторые изменения, чтобы сделать его более понятным (см. combinations):

#!/usr/bin/perl

use strict;
use warnings;

sub c {
   my $n=-1+shift;
   $n ? map{
             my $c = $_;
             map $c . $_ , c($n ,@_)
           } @_
   : @_;
}

sub combinations {
   my $number = shift; # remove the first item from @_
   my @chars  = @_;    # the remainder of @_

   $number --; # decrement $number, so that you will eventually exit
               # from this recursive subroutine (once $number == 0)

   if ($number) { # true as long as $number != 0 and $number not undef

      my @result;

      foreach my $char (@chars) {
         my @intermediate_list = map { $char . $_ } combinations($number, @chars);
         push @result, @intermediate_list;
      }

      return @result; # the current concatenation result will be used for creation of
                      # @intermediate_list in the 'subroutine instance' that called 'combinations'
   }
   else {
      return @chars;
   }
}

print join " ", combinations(2, "A", "B");
print "\n";
print join " ", c(2, "A", "B");
print "\n\n";
print join " ", combinations(3, "A", "B");
print "\n";
print join " ", c(3, "A", "B");
print "\n";

Обе версии работают одинаково и выдают одинаковый результат:

AA AB BA BB
AA AB BA BB

AAA AAB ABA ABB BAA BAB BBA BBB
AAA AAB ABA ABB BAA BAB BBA BBB

Я включил некоторые комментарии в код, но, возможно, нужно более подробное объяснение!? Что ж, вот пример, иллюстрирующий, как все работает: допустим, у нас есть два элемента, «А» и «Б», и мы хотим получить все возможные комбинации из двух этих элементов. В таком случае $number изначально будет равно 2 (так как мы хотим получить пары), а @chars будет равно ('A', 'B').

При первом вызове combinations $number уменьшается до 1, таким образом выполняется условие if, и мы входим в цикл foreach. Это сначала устанавливает $char в «A». Затем он вызывает combinations(1, ('A', 'B')). Поскольку $number всегда уменьшается при вызове подпрограммы, $number равно 0 в этой «дочерней подпрограмме», следовательно, дочерняя процедура просто возвращает («A», «B»). Таким образом:

@intermediate_list = map { $char . $_ } ('A', 'B'); # $char eq 'A'

Затем map берет как «A», так и «B» и объединяет каждый с «A» ($ char), таким образом, @intermediate_list есть ( «AA», «AB»). В следующем раунде цикла foreach то же самое делается с $char = B, что устанавливает @intermediate_list в ('BA', 'BB').

В каждом раунде содержимое @intermediate_list помещается в список результатов, поэтому @result в итоге содержит все возможные комбинации.

Если вы хотите получить тройки вместо пар, вы, очевидно, начнете с $number = 3, а combinations будет вызываться три раза. При втором вызове он вернет @result, то есть список, содержащий пары. Каждый элемент из этого списка будет объединен с каждым символом исходного набора символов.

Ладно, надеюсь, это имеет смысл. Спрашивайте, если что-то непонятно.

EDIT: см. комментарий ysth ниже.