Well, I read Deque's tut for creating all possible combinations of elements from a set
here, wrote my own implementation in C. And then added ability to generate only the permutations of the set elements.
I'll recommend going through Deque's tutorial before reading the following.
I've implemented the SEPA algorithm described
here. It's a pretty good algorithm considering it's O(n) (there aren't many algos for creating perms with O(n)) and doesn't require additional data structures for permuting a common
type of data, i.e. you can permute abcd to all the 4! permutations but with sets like, say, abcd015 it won't work as it needs a bigger than|less that relation b/w the elements.
So, I used the algorithm on the indices' array instead which gives me the correct result. That was rather easy.
Problem was with generating all possible permutations of the set
within a given length.
Now, the first permutation always has the element with lowest value at the extreme left and ascend towards the right. For example, the first permutation of the character set 'abcd' would be 'abcd'. 'a' the lowest value, 'd' being the highest. Or, if you think about the indices (of the current perm), it's 0123.
[ In contrast, the last permutation would be 'dcba', in indices, 3210 which has the exact opposite property. ]
Now, for length 3, you'd want to permute only 3 of them at a time, and eventually get all possible perms i.e. 4p3 = 24 perms.
Basically, you have to look for indices that are in ascending order. I'll explain.
In this example (abcd, with length 3), indices with ascending order are:
012 abc
013 abd
023 acd
123 bcd
Now, using these strings as the beginning/first perms, we can create all the perms of these strings with the SEPA algorithm and in the process we can get all 4p3 perms.
The ascending properry is easy to examine by checking the returned indices in pairs.
for (; start<maxwords; start++) {
get_indices(str_indices, start, len+1, maxlen);
bool got_first_permute = true;
for (j=0; j<maxlen-1; j++) {
/* the candidates for further permutations 'd have to be in acs
sorted oeder. these are the first perms of the groups */
if (str_indices[j] >= str_indices[j+1]) {
got_first_permute = false;
break;
}
}
if (got_first_permute) {
<generate their permutations>
.
.
}
This goes on upto the last such indice array i.e. 123.
So, to check if it's the last such string to permute on, we do a sum of the indices, and check that with the highest possible sum of indices for the entire string.
i.e. for 0123, the highest is 1+2+3 which can also be calculated as sum of the A.P. series 1,2,3 like n/2(a+l) , n being the number of terms, a and l being the first and last elements respectively.
We do this in the program like this:
int max_sum = (int)ceil((float)maxlen/2.0) * (2*len-maxlen+1);
Because, we're using integers, the sum 'd be higher than if done with float when maxlen is odd.
Here's how the check is performed:
inline int get_sum(int *arr, int ub)
{
int sum=0;
while (ub)
sum += arr[ub--];
return sum+arr[ub];
}
/* in main */
.
.
if (got_first_permute) {
/* the last cadidate will have indices (len-maxlen+1),(len-maxlen),...len */
if(get_sum(str_indices, maxlen-1) == max_sum)
complete = true;
gen_permutes(tmp, str_indices, maxlen);
}
if (complete) break;
.
.
This is how our output 'll look for length 3 on 'abcd'
abc
acb
bac
bca
cab
cba
abd
adb
bad
bda
dab
dba
acd
adc
cad
cda
dac
dca
bcd
bdc
cbd
cdb
dbc
dcb
Similarly, in case of permuting over 'abcde' with length of 3, the starting strings would be
012 abc
013 abd
014 abe
023 acd
024 ace
034 ade
123 bcd
124 bce
134 bde
234 cde
In this case, max_sum will be 12, instead of 9. Last string to permute on will have indices 234.
And number of permutations 'd be 5p3 = 60
This way, all permutations of a set over a specified length can be obtained.
Here's the entire code:
/*
program to generate 1. all possible combinations
2. all possible permutations
of either a specified lenght or of the lenght of
the given set.
for gcc, compile with gcc -lm
Usage: program_name options args
args:
-c create combinations
-p " permutations
-l <lenght> generate strings only of the specified length.
can be ommited
Example:
./a.out -l3 -p abcd
./a.out -l3 -c abcd
./a.out -c abcd
./a.out -p abcd
Author :: Opoitr [ evilzone.org ]
Permission granted for modification and redistribution of code in any format.
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <string.h>
#include <math.h>
/* generates indices for the current sequence */
void get_indices(int *str_ind, long seq, int rad, int maxlen)
{
register int i = maxlen-1;
/*printf("%d\n", i);*/
long tmp_seq = seq;
while (i > 0) {
if (tmp_seq > 0) {
str_ind[i--] = (tmp_seq % rad);
tmp_seq /= rad;
}
else
str_ind[i--] = 0;
}
str_ind[i] = tmp_seq;
}
/* generates all possible combinations */
void gen_strings(const char *buff, int maxlen)
{
int rad = strlen(buff);
int str_indices[maxlen];
register long i=0, j;
long maxwords = (long)pow(rad, maxlen);
for (; i<maxwords; i++) {
get_indices(str_indices, i, rad, maxlen);
for (j=0; j<maxlen; j++)
printf("%c", buff[str_indices[j]]);
puts("");
}
}
void swap(int *arr, int key, int swap_ind)
{
int temp = arr[swap_ind];
arr[swap_ind] = arr[key];
arr[key] = temp;
}
/* permutation */
void gen_permutes(const char *buff, int *str_indices, int maxlen)
{
long i=0, j;
/* printf first permute */
for (j=0; j<maxlen; j++)
printf("%c", buff[str_indices[j]]);
puts("");
/* Using the SEPA algorithm */
/* find subsequent permutations */
while (1) {
/* find key */
int key=0;
for (i=maxlen-1; i>0; i--) {
if (str_indices[i-1] < str_indices[i]) {
key = i-1;
break;
}
else key = -1;
}
if (key < 0) return; /* if no key found, already at last permutatiom. return. */
/* where to swap key with */
int swap_ind;
for (i=maxlen-1; i>key; i--) {
if (str_indices[i] > str_indices[key]) {
swap_ind = i;
break;
}
}
swap(str_indices, key, swap_ind);
/* re-sort tail to ascending */
for (i=++key, j=maxlen-1; i<j; i++, j--)
swap(str_indices, i, j);
/* print */
for (j=0; j<maxlen; j++)
printf("%c", buff[str_indices[j]]);
puts("");
}
}
/* returns sum of the current indices */
inline int get_sum(int *arr, int ub)
{
int sum=0;
while (ub)
sum += arr[ub--];
return sum+arr[ub];
}
int main(int argc, char **argv)
{
if (argc<2 /*|| (argc == 3 && !isdigit(*argv[2]))*/) {
puts("Wrong args!");
exit(1);
}
char temp;
char *tmp;
register int maxlen = 0;
while((temp = getopt(argc, argv, "l:p:c:")) != -1) {
switch (temp) {
case 'l':
if (tmp = optarg)
maxlen = atoi(tmp);
break;
case 'p':
if (tmp = optarg) {
int len = strlen(tmp);
if (!maxlen) {
int str_indices[len], i;
/* first permutation indexes */
for (i=0; i<len; i++)
str_indices[i] = i;
gen_permutes(tmp, str_indices, len);
}
else {
int start=0, j;
int str_indices[maxlen];
int len = strlen(tmp)-1;
if (maxlen > len) {
printf("Length must be <= given string length for permutation!\n");
return 1;
}
/* sum of the A.P. len-maxlen+1 to len : mxln/2 * (len + len-maxlen+1) */
int max_sum = (int)ceil((float)maxlen/2.0) * (2*len-maxlen+1);
int maxwords = (int)pow(len+1, maxlen);
bool complete = false;
/* each pass, we find the first perm indeces of a group and
permute the group farther with gen_permutes() */
while (1) {
for (; start<maxwords; start++) {
get_indices(str_indices, start, len+1, maxlen);
bool got_first_permute = true;
for (j=0; j<maxlen-1; j++) {
/* the candidates for further permutations 'd have to be in acs
sorted oeder. these are the first perms of the groups */
if (str_indices[j] >= str_indices[j+1]) {
got_first_permute = false;
break;
}
}
if (got_first_permute) {
/* the last cadidate will have indices (len-maxlen+1),(len-maxlen),...len */
if(get_sum(str_indices, maxlen-1) == max_sum)
complete = true;
gen_permutes(tmp, str_indices, maxlen);
}
if (complete) break;
}
break;
}
}
}
break;
case 'c':
if (tmp = optarg) {
if(!maxlen)
gen_strings(tmp, strlen(tmp));
else
gen_strings(tmp, maxlen);
}
break;
}
}
return 0;
}
