stephenbrooks.orgForumTalkSensibleAlgorithms - string array combinations
Username: Password:
Search site:
Subscribe to thread via RSS
tgkprog
2008-04-04 00:18:23
i have a sorted list of words
can someone come up with a algorithm for combinations of two or more words seperated by space?

it can be unique,

example
home
ran
tom

Answer

home ran
home tom
ran tom
home ran tom

note :
1. order is not important so the answer should not have 'home ran tom' and 'home tom ran' only 1 of them
2. the answer set can have 'home ran' or 'ran home' but not both meaning the order of the words can be any in the final line items but each line item should contain unique set of words

combinations have to include 2 and larger sets so if there are 4 words:
fast
home
ran
tom

Answer:
fast home
home ran
ran tom
fast ran
home tom
fast tom
fast home ran
home ran tom
fast home tom
fast home ran tom

http://en.wikipedia.org/wiki/Permutation#Counting_permutations has background, but above me to make a algorithm.

super would be working code in c or java or vba (anyone who has excel can do it then!)

thank you
Stephen Brooks
2008-04-05 18:08:26
You missed "fast ran tom" from the second list I think?

What you do is for N words, form all binary numbers of N bits.  So for N=4:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

And then exclude 0000, 0001, 0010, 0100, 1000 (i.e. 0 and powers of two with only 1 bit set).  Then use each remaining number's bits to determine whether to add a word to the list:

0011 = ran tom
0101 = home tom
0110 = home ran
0111 = home ran tom
1001 = fast tom
1010 = fast ran
1011 = fast ran tom
1100 = fast home
1101 = fast home tom
1110 = fast home ran
1111 = fast home ran tom
Stephen Brooks
2008-04-05 18:12:03
C code:
int n,i;
char *words[]={"fast","home","ran","tom"}; int m=sizeof(words)/sizeof(*words);
for (n=(1<<m)-1;n>0;n--) if (n&(n-1))
{
for (i=m-1;i>=0;i--) if (n&(1<<i)) printf(" %s",words[i]);
printf("\n");
}
tgkprog
2008-04-07 02:46:37
Mallards are great and you are brilliant !  thank you trying to understand the code now
: contact : - - -
E-mail: sbstrudel characterstephenbrooks.orgTwitter: stephenjbrooksMastodon: strudel charactersjbstrudel charactermstdn.io RSS feed

Site has had 26587428 accesses.