use strict;
use warnings;
use Data::Dumper;

my @menge = 1 .. 4;
my @iter  = rec(@menge);

print Dumper \@iter;

sub rec {
    return () unless ( @_ > 1 );
    my $first = shift;
    map {
        my ( $second, $rest ) = @$_;
        [ [ $first, $second ], $rest ? @$rest : () ]
    } map {
        my @tmp        = @_;
        my ( $second ) = splice @tmp, $_, 1;
        [ $second, rec(@tmp) ]
    } 0 .. @_ - 1
}