29 December 2014

Quiz 71: Print all combinations of a sentence

Problem:

Given a sentence like "i love perl", print all sentences that can be formed using all words from original sentence.

Input Format: 

A Sentence where words are seprated by single space


Output Format: 

All combinations in different lines


Constraints: 

none

Sample Input

I love perl

Sample Output:

I love perl
I perl love
perl I love
perl love I
love I perl
love perl I

Explanations:

sentence have 3 words , so 6 different combinations



Solution:

chomp($line=<STDIN>);
@array=split(" ",$line);

sub fact {
   my $tmp = shift;
   return 1 if $tmp < 2;
   return $tmp*fact($tmp-1);
}

my %seen;
$len=@array;
$count = fact($len);
$nr  = 0;
while( $nr < $count ) {
    $var = 1;
    @arr;
    while( $var ) {
        for( my $i = 0; $i < $len; ++$i ) {
            $arr[$i] = $array[ rand $len ];
        }
        my %unique;
        my $unique = 1;
        for my $c ( @arr ) {
            if( ++$unique{$c} > 1 ) {
                $unique = 0;
            }
        }
        if( $unique == 1 ) {
            $var = 0;
        }
    }

    if( exists $seen{ "@arr" } ) {
        next;
    }
    else {
        local $" = "\t";
        foreach(@arr)
{
print "$_ ";
}
print "\n";
    }
    ++$seen{"@arr"};
    ++$nr;
}

Tips:

Use factorial to find number of combinations

No comments:

Post a Comment