Gene said:
Robert Hayes said:
I have code that will take a string and generate the permutations
of the string. [...snip...]
What I would like is to modify it so it can produce:
a
b
c
ab
ac
ba
bc
ca
cb
abc
acb
bac
bca
cab
cba
I would like to work this out for myself so all I would like
is some pseudo code please.
If you don't want the C, then this isn't really a C question,
but okay...
It looks like you want to compose two algorithms, finding all
permutations of all combinations. You already how how to do
the first. To enumerate the combinations of n things taken m
at a time, an easy algorithm is to choose each item i = 0 to
n-m in succession and then recursively choose m-1 items from
the remaining items in the range i+1 to n-1. The base cases
are straightforward: When m>n, do nothing. This is impossible.
When m==0, output all choices thus far. In this case rather
than producing the combination as output immediately, you'll
be feeding the combination to your permutation generator.
If you have repeated letters in the original string, you need to
be careful about duplication. For instance, starting with abaca,
three selections of two letters produce aa.
You can avoid this by counting unique letters and recursively
iterating over those unique letter counts. The code below does
this by sorting the string and treating repeated letters as one
block. Apart from that, it's Gene's algorithm.
% type pc.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* take permute function as read...*/
void swap(char *p, char *q) { char t = *p; *p = *q; *q = t;
} void reverse(char *p, char *q) { if (p != q) for(; p <
--q; p++) swap(p, q); } int permute(char *p, char *q) { char
*r, *s, *t; if (p == q) return 0; for (r = q - 1; p < r; ) {
s = r--; if (*r < *s) { t = q; while (*r >= *--t) ; swap(r,
t); reverse(s, q); return 1; } } reverse(p, q); return 0; }
void dist(char *sub, size_t i, size_t n, char *curr)
{
if (i == n)
{
sub[n] = 0;
do { puts(sub); } while (permute(sub, sub + n));
}
else if (strlen(curr) < n - i)
return;
else
{
size_t c, d, z;
char *next = strrchr(curr, *curr) + 1;
z = next - curr;
if (n - i < z) z = n - i;
for (d = 0; d < z; d++)
sub[i + d] = *curr;
for (c = z + 1; c-- > 0; )
dist(sub, i + c, n, next);
}
}
int cmp(const void *lv, const void *rv)
{
const char *lc = lv;
const char *rc = rv;
return (*lc > *rc) - (*lc < *rc);
}
int main(int argc, char **argv)
{
char sub[42]; /* big enough! */
if (argc > 1)
while (argv++, --argc)
{
size_t n, z = strlen(*argv);
printf("\n%s:\n", *argv);
if (sizeof(sub) - 1 < z) { puts("too long!"); continue; }
qsort(*argv, z, 1, cmp);
for (n = 1; n <= z; n++)
dist(sub, 0, n, *argv);
}
return 0;
}
% acc pc.c -o pc.exe
% pc abc aaabb
abc:
a
b
c
ab
ba
ac
ca
bc
cb
abc
acb
bac
bca
cab
cba
aaabb:
a
b
aa
ab
ba
bb
aaa
aab
aba
baa
abb
bab
bba
aaab
aaba
abaa
baaa
aabb
abab
abba
baab
baba
bbaa
aaabb
aabab
aabba
abaab
ababa
abbaa
baaab
baaba
babaa
bbaaa
%
