Как мне абстрагировать несколько вложенных циклов? - PullRequest
Новая
       5

Как мне абстрагировать несколько вложенных циклов?

0 голосов
/ 30 декабря 2018

Учитывая, разбивая массив на p частей размером ≥ 1 каждая: 

my @a = 'A'..'F';

# p = 1
my @p1 = [@a];
# ["A" .. "F"]

# p = 2
my @p2;
for my $x (0..@a-2) {
    push @p2, [
        [@a[0..$x]],
        [@a[$x+1..@a-1]],
    ];
}
# [["A"], ["B" .. "F"]],
# [["A", "B"], ["C" .. "F"]],
# [["A", "B", "C"], ["D", "E", "F"]],
# [["A" .. "D"], ["E", "F"]],
# [["A" .. "E"], ["F"]],


# p = 3
my @p3;
for my $x (0..@a-3) {
    for my $y ($x+1..@a-2) {
        push @p3, [
            [@a[0..$x]],
            [@a[$x+1..$y]],
            [@a[$y+1..@a-1]],
        ];
    }
}
# [["A"], ["B"], ["C" .. "F"]],
# [["A"], ["B", "C"], ["D", "E", "F"]],
# [["A"], ["B", "C", "D"], ["E", "F"]],
# [["A"], ["B" .. "E"], ["F"]],
# [["A", "B"], ["C"], ["D", "E", "F"]],
# [["A", "B"], ["C", "D"], ["E", "F"]],
# [["A", "B"], ["C", "D", "E"], ["F"]],
# [["A", "B", "C"], ["D"], ["E", "F"]],
# [["A", "B", "C"], ["D", "E"], ["F"]],
# [["A" .. "D"], ["E"], ["F"]],


# p = 4
my @p4;
for my $x (0..@a-4) {
    for my $y ($x+1..@a-3) {
        for my $z ($y+1..@a-2) {
            push @p4, [
                [@a[0..$x]],
                [@a[$x+1..$y]],
                [@a[$y+1..$z]],
                [@a[$z+1..@a-1]],
            ];
        }
    }
}
# [["A"], ["B"], ["C"], ["D", "E", "F"]],
# [["A"], ["B"], ["C", "D"], ["E", "F"]],
# [["A"], ["B"], ["C", "D", "E"], ["F"]],
# [["A"], ["B", "C"], ["D"], ["E", "F"]],
# [["A"], ["B", "C"], ["D", "E"], ["F"]],
# [["A"], ["B", "C", "D"], ["E"], ["F"]],
# [["A", "B"], ["C"], ["D"], ["E", "F"]],
# [["A", "B"], ["C"], ["D", "E"], ["F"]],
# [["A", "B"], ["C", "D"], ["E"], ["F"]],
# [["A", "B", "C"], ["D"], ["E"], ["F"]],

Как мне абстрагироваться от увеличивающегося числа вложенных циклов, чтобы превратить его в суб slices(Int $p, Array @a)?Я думаю, мне нужен какой-то более высокий порядок foreach.

Ответы [ 2 ]

0 голосов
/ 31 декабря 2018

Вы хотите Algorithm :: Loop NestedLoops, когда вам нужно произвольное количество вложенных циклов. 

use Algorithm::Loops qw( NestedLoops );

sub list_segments {
   my ($array, $p) = @_;

   my $iter = NestedLoops([
      [ 0 ],
      ( map { my $d = $_;   sub { [ $_+1 .. @$array-($p-$d) ] }   } 1 .. $p-1 ),
      [ 0+@$array ],
   ]);

   return sub {
      my @split_points = $iter->()
         or return ();

      return [
         map [ @$array[ $split_points[$_] .. $split_points[$_+1]-1 ] ],
            0..$#split_points-1
      ];
   };
}

Это можно проверить с помощью следующего: 

use Data::Dump qw( dd );

my $iter = list_segments(['A'..'F'], 3);
while ( my $list_segments = $iter->() ) {
   dd($list_segments);
}

Вывод: 

[["A"], ["B"], ["C" .. "F"]]
[["A"], ["B", "C"], ["D", "E", "F"]]
[["A"], ["B", "C", "D"], ["E", "F"]]
[["A"], ["B" .. "E"], ["F"]]
[["A", "B"], ["C"], ["D", "E", "F"]]
[["A", "B"], ["C", "D"], ["E", "F"]]
[["A", "B"], ["C", "D", "E"], ["F"]]
[["A", "B", "C"], ["D"], ["E", "F"]]
[["A", "B", "C"], ["D", "E"], ["F"]]
[["A" .. "D"], ["E"], ["F"]]

Кстати, простой способ проверить решения - сравнить количество результатов с C (N-1, p-1) = (N-1)!/ (Np)!/ (п-1)!поскольку вы эффективно выбираете точки разделения p-1 из возможных точек разделения N-1.

0 голосов
/ 31 декабря 2018

Вы можете искать рекурсивное решение?

Для p = 1 slices просто возвращает все элементы вместе.Для p > 1 он берет первые n элементов и объединяет элементы для p - 1 для каждого 1 <= <em>n <количество элементов. </p> 

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dump qw(dump);

my @a = 'A' .. 'F';

for (my $i = 1; $i <= 4; $i++) {
  warn("p = $i\n");
  dump(slices($i, @a));
};

sub slices
{
  my $p = shift();
  my @a = @_;

  my @ret;

  if ($p == 1) {
    push(@ret, [[@a]]);
  }
  else {
    for (my $i = 0; $i < $#a; $i++) {
      foreach (slices($p - 1, @a[($i + 1) .. $#a])) {
        push(@ret, [([@a[0 .. $i]], @{$_})]);
      }
      # or shorter:
      #push(@ret, map({[([@a[0 .. $i]], @{$_})]} slices($p - 1, @a[($i + 1) .. $#a])));
    }
  }

  return @ret;
}

Вывод: 

p = 1
[["A" .. "F"]]
p = 2
(
  [["A"], ["B" .. "F"]],
  [["A", "B"], ["C" .. "F"]],
  [["A", "B", "C"], ["D", "E", "F"]],
  [["A" .. "D"], ["E", "F"]],
  [["A" .. "E"], ["F"]],
)
p = 3
(
  [["A"], ["B"], ["C" .. "F"]],
  [["A"], ["B", "C"], ["D", "E", "F"]],
  [["A"], ["B", "C", "D"], ["E", "F"]],
  [["A"], ["B" .. "E"], ["F"]],
  [["A", "B"], ["C"], ["D", "E", "F"]],
  [["A", "B"], ["C", "D"], ["E", "F"]],
  [["A", "B"], ["C", "D", "E"], ["F"]],
  [["A", "B", "C"], ["D"], ["E", "F"]],
  [["A", "B", "C"], ["D", "E"], ["F"]],
  [["A" .. "D"], ["E"], ["F"]],
)
p = 4
(
  [["A"], ["B"], ["C"], ["D", "E", "F"]],
  [["A"], ["B"], ["C", "D"], ["E", "F"]],
  [["A"], ["B"], ["C", "D", "E"], ["F"]],
  [["A"], ["B", "C"], ["D"], ["E", "F"]],
  [["A"], ["B", "C"], ["D", "E"], ["F"]],
  [["A"], ["B", "C", "D"], ["E"], ["F"]],
  [["A", "B"], ["C"], ["D"], ["E", "F"]],
  [["A", "B"], ["C"], ["D", "E"], ["F"]],
  [["A", "B"], ["C", "D"], ["E"], ["F"]],
  [["A", "B", "C"], ["D"], ["E"], ["F"]],
)

(Может потребоваться несколько настроек. Например, проверка 1 <= <em>p <= количество предметов.) </p>

...