Efficiently creating a sequential wordlist from charset

Question

I need to find an efficient way to create a list of sequential words created from a given charset in C/C++. Let me give you an example:

If the charset is "abc", the algorithm should output:

  a
  b
  c
 aa
 ab
 ac
 ba
 bb
 bc
 ca
 cb
 cc
aaa
aab 
...

I have some ideas, but all are require too much maths and I really need a fast solution. Who's got an idea?

I'm getting a lot of ideas but they all boil down to really being brute force with minor efficiency gains. Like taking that and making a string AAABBBCCC and just sort of moving though it in 3 chunks Until I get back to the beginning (Linking them together like a Link List): AAA,AAB,ABB,BBB,BBC,BCC,CCC,CCA,CAA. Then going back the other way Only Adding the new ones: CCB,CBB,BBA,BAA,AAC,ACC Next be AABBCC: AA,AB,BB,BC,CC,CA Then: CB,BA,AC Then ABC: A,B,C. But that doesn't get the mixed up cases. Good luck finding an efficient way. — Cericme, Jul 13 '12 at 20:14

score 2 · Answer 1 · edited May 23 '17 at 10:09

2

This is really a slight modification on this answer:

What is optimal algorithm to make all possible combinations of a string?

With the above answer you could put a wrapper around the routine that essentially does permutations of the main input string letting the perutation finder find all the permutations of your pre-permuted input strings.

edited May 23 '17 at 10:09

Community

1
1

answered Jul 13 '12 at 20:06

trumpetlicks

7,033
2
19
33

BLUEPIXY · Accepted Answer · 2012-07-14T17:56:14.403

#include <stdio.h>
#include <string.h>

char* numToColumn(int n, char* outstr, const char* baseset){
    char* p = outstr;
    int len;
    len = strlen(baseset);
    while(n){
        *p++ = baseset[0 + ((n % len == 0)? len : n % len) - 1];
        n = (n - 1) / len;
    }
    *p = '\0';
    return strrev(outstr);//strrev isn't ANSI C
}

char* incrWord(char* outstr, const char* baseset){
    char *p;
    int size,len;
    int i,carry=1;

    size = strlen(baseset);
    len = strlen(outstr);
    for(i = len-1; carry && i>=0 ;--i){
        int pos;
        pos = strchr(baseset, outstr[i]) - baseset;//MUST NOT NULL
        pos += 1;//increment
        if(pos == size){
            carry=1;
            pos = 0;
        } else {
            carry=0;
        }
        outstr[i]=baseset[pos];
    }
    if(carry){
        memmove(&outstr[1], &outstr[0], len+1);
        outstr[0]=baseset[0];
    }
    return outstr;
}

int main(){
    const char *cset = "abc";
    char buff[16];
    int i;

    for(i=1;i<16;++i)//1 origin
        printf("%s\n", numToColumn(i, buff, cset));

    strcpy(buff, "cc");//start "cc"
    printf("\nrestart\n%s\n", buff);
    printf("%s\n", incrWord(buff, cset));
    printf("%s\n", incrWord(buff, cset));
    return 0;
}
/* RESULT:
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac

restart
cc
aaa
aab
*/

score 0 · Answer 3 · answered Jul 16 '12 at 13:10

The following java code works fine.

class Combination
{
static String word;
static int length;
static int[] num;
public static void main(String args[])
{
word = "abc";
length = word.length();
num = new int[length + 1];
for(int i=1; i<=length-1; i++)
    num[i] = 0;
    num[length] = 1;        
    while(num[0] == 0)
    {
        display();
        System.out.println();
        increment(length);
    }
}
public static void increment(int digit)
{
    if(num[digit] + 1 <= length)
        num[digit]++;
    else
    {
        num[digit] = 1;
        increment(digit-1);
    }
}
public static void display()
{
    for(int i=1; i<=length; i++)
    {
        if(num[i] == 0)
            System.out.print(' ');
        else
            System.out.print(word.charAt(num[i]-1));
    }
}
}

I'm not sure about its complexity. But I don't think it has a high complexity.

If you want to show all the combinations, then you would have to use brute-force method. This is like counting. For 3 digit numbers, you can use 4-ary numbers (0, 1, 2, 3). For n-digits, you can use (n+1)-ary (1, 2, 3... n+1) numbers with 0 representing empty space. For "abc", cases can be 001 002 003 010 and so on. with 0 -> null, 1 -> 'a', 2 -> 'b', 3 -> 'c' An extra left-digit can be taken and set to 0. The loops continues while it is 0. Whenever it turns '1', the loop stops. So, +1 to the length of the array. Struggling to write this in the answer... Giving an error. — Shashwat, Jul 16 '12 at 13:13

Efficiently creating a sequential wordlist from charset

3 Answers3

Linked