blob: b5f0bf811d940fb74e442f476d4b4c02f5029951 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#!/usr/bin/env perl
use strict;
use warnings;
use 5.016;
sub factorial {
my ($n) = @_;
return 1 if $n < 2;
return $n * factorial($n - 1);
}
sub permutations {
my ($n) = @_;
my $string = join('', 1..$n);
return map { _permutation($string, $_) } 0..(factorial($n) - 1);
}
sub _permutation {
my ($string, $index) = @_;
return '' if $string eq '';
my $fact = factorial(length($string) - 1);
my $current_index = int($index / $fact);
my $rest = $index % $fact;
my $first_digit = substr($string, $current_index, 1);
substr($string, $current_index, 1, '');
return $first_digit . _permutation($string, $rest);
}
sub apply_signs {
my ($list) = @_;
my $len = @$list;
my @ret;
for my $n (0..(2 ** $len - 1)) {
my @coefs = map { $_ ? 1 : -1 } split '', sprintf("%0${len}b", $n);
push @ret, [ map { $list->[$_] * $coefs[$_] } 0..($len - 1) ];
}
return @ret;
}
my $n = <>;
say factorial($n) * (2 ** $n);
say join(' ', @$_) for map { apply_signs($_) } map { [split ''] } permutations($n);
|