1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include<stdio.h>
#include<stdlib.h>
/* chouse_n ( char *strng, int length) returns a pointer to a string of */
/* length characters chosen from "strng" , duplicate chars in "strng" are */
/* significant. Strings are generated in lexical order. */
/* First call, call with *strng. each subsiquent call, call with NULL, */
/* returns one combination. Calls after all combinations have been */
/* returned return NULL. Will return NULL for errors. */
/* not very defensive (i.e. WILL BREAK) */
/* dave chapman aug '91 released to public domain */
char *chouse_n( char *strng, int length);
char *chouse_n( char *strng, int length)
{
static char *str;
static char *curr;
static char *pos; /* for each char in curr(ent string),
its pos in str */
static int counts[256];
int i,j;
if (0 >= length)
return NULL;
if (NULL != strng)
{
str = malloc(strlen(strng)); /* first call, prep string for use */
curr = malloc(2 * length + 1);
pos = curr + length +1;
for (i = 0; i < 256; counts[i++] = 0)
;
for (i = 0; strng[i]; i++)
counts[strng[i]]++;
for (i = 1, j = 0; i < 256; i++)
{
if (counts[i])
{
str[j] = i;
counts[j++] = counts[i];
}
}
str[j] = '\0'; /* str is string of distinct chars in order */
/* counts[] holds count of each char */
/* take first length chars */
for (i = 0,j = 0; i < length; i++)
{
curr[i] = str[j];
pos[i] = j;
if (!(--counts[j]))
j++;
}
curr[i] = '\0';
return curr;
}
/* if called with "mississippi",5;
str -> "imps"
curr -> "iiiim"
counts -> 0,0,2,4;
pos -> 0,0,0,0,1; */
/* go back to front */
for (j = length; j > 0;)
{
counts[ pos[--j]]++; /* "replace" char */
/* look for a new char for curr posit. */
for ( i = ++pos[j]; str[i] && ! counts[i]; i++)
;
if (0 != (curr[j] = str[i])) /* found a char */
{
--counts[i];
pos[j] = i;
/* placed char, fill out rest of string */
for (++j, i = 0; j < length; j++)
{
for ( ; !counts[i]; i++)
;
curr[j] = str[i]; /* first available char */
--counts[i];
pos[j] = i;
}
return curr;
}
/* no more chars for this pos ; go back one */
}
/* done */
return NULL;
}
void main(void)
{
char *str = "aabbccdd";
int i,j;
j = 0;
i = 5;
puts(chouse_n( str, i));
while (NULL != (str = chouse_n(NULL, i)))
{
++j;
printf(" %s %d\n",str,j);
}
}
|
