Thomas Cameron wrote:
I have an array of values which I would like to generate all
possible combinations for. And example would be the values "a,b,c".
This would produce the following:
a
ab
abc
ac
b
bc
c
Does anybody know of the algorithm to produce this? I've seen the
topic discussed, but never for strings or anything of the such. Most
discussion is regarding calculating the number of combinations...
which I don't care about.
I've published this before in this group. Combining it with the
following alias is useful:
[1] c:\c\jumble>ali as jumble
\c\jumble\jumbl e %1& | sort | uniq | pr -a -T --columns=8
---------------- cut here for jumble.c ---------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */
/* Things get out of hand when larger than 8 */
#define MAXWORD 12
/* ------------------ */
/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;
c = *wd;
*wd = wd[i];
wd[i] = c;
} /* trade */
/* ------------------ */
/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;
if (0 == n) {
outstring[ix] = '\0';
puts(outstring) ;
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */
/* ------------------ */
int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];
if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword> [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';
min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;
for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;
fprintf(stderr, "string=\"% s\", max=%.0f, len=%u\n",
argv[1], max, min);
jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main, jumble.c */
--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson