use strict;
use warnings;

my $n = shift;    # Anzahl Tage; -> 2*n Fächer
die "Anzahl Tage übergeben\n" unless $n > 0;
die "OMG, viel zu lang!\n" unless $n <= 10;

my $z;    # Zähler

# sub plan ist die rekursive Funktion
# Sie sammelt im ersten Arg das ein, was bereits verplant ist und 
# die restlichen Args sind noch freie Fächer (Nummern)
plan ([], 1 .. 2*$n);
print "$z verschiedene\n";

sub plan {
    my @p = @{shift @_};    # Das steht derzeit fest
    # Ausgeben, wenn nichts mehr zu verteilen ist.
    ++$z, return print join ('', map {$_&1 ? "$p[$_]}" : "{$p[$_],"} 0 .. $#p) . "\n" unless @_;
    # Aus den freien den ersten wählen.
    # Iterieren über die Positionen.
    foreach my $i (0 .. $#_-1) {
        # Aus den verbleibenen (größeren, wg Kanonizität) den
        # 2. wählen
        # Iterieren über restlichen (höheren) Indexnummern
        foreach my $j ($i+1 .. $#_) {
            # Rekursion mit den neu festgelegten gemerkt,
            # und dem verbleiben Rest zur Auswahl
            plan ([@p,$_[$i],$_[$j]], @_[0 .. $i-1], @_[$i+1 .. $j-1], @_[$j+1 .. $#_]);
        }
    }
}