29 December 2014

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

none

I love perl

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