EvilZone
Programming and Scripting => C - C++ => : 0poitr April 14, 2013, 10:53:43 PM
-
Well, I read Deque's tut for creating all possible combinations of elements from a set here (https://evilzone.org/tutorials/(tut)-create-a-wordlist-generator-(i-e-for-bruteforcing)), 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 (http://www.freewebs.com/permute/soda_submit.html). 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;
}
-
Good work, Opoitr. I don't see anything of my algorithm anymore, though.
Your main function looks scary.
-
Good work, Opoitr. I don't see anything of my algorithm anymore, though.
Your main function looks scary.
Well, get_indices() and gen_strings() in my code is equivalent to convertToRadix() and generate() in yours. And yes, the main()'s a bit clumsy. I put all the checks for finding starting permutations in the switch case :P
-
@0poitr; in your main(), you're declaring 'maxlen' as a register without changing that length and later using a normal int as an iterator. I'd suggest swapping the two. If possible, you may consider adding the 'unsigned' qualifier where applicable. You could also, potentially, benefit from a performance increase by using pre-increment rather than post-increment. The reason is that the pre-increment operation is usually guaranteed to be no slower than post-increment but it could possibly be faster. Check your usage, though, to make sure you're not depending on an existing state before the increment.
Otherwise, not bad. It's always good to try to optimize, though.
-
@0poitr; in your main(), you're declaring 'maxlen' as a register without changing that length and later using a normal int as an iterator. I'd suggest swapping the two.
The register one is a good suggestion. I made start and j register instead.
But what do you mean by 'without changing that length' ?
I generally try to avoid unsigned loop variables because if they are to be decremented, it might go _very_ bad. You know why.
And, Thanks.
-
i like what u said bro