Algorithm Problem

Attention: This is absolutely not a homework :D

By the way, I just confused about how to solve this kind of problem.
What should I use? Iteration(I don't think so), recursive function(perhaps) or gotos :(

Ok, here we go.

Test case 1:
Given input:

Code:

---

characters: [a, b]
maximum length: 2

---

And the output is:

Code:

---

a aa ab b ba bb

---

The order is unnecessary.

Test case 2:

Code:

---

characters: [a, b]
maximum length: 3

---

vvv

Code:

---

a aa ab b ba bb aaa aab aba abb baa bab bba bbb

---

Test case 3:

Code:

---

characters: [a, b, c]
 maximum length: 2

---

vvv

Code:

---

a aa ab ac b ba bb bc

---

Test case 4:

Code:

---

characters: [a, b, c, d, e]
 maximum length: 1

---

vvv

Code:

---

a b c d e

---

I tried to write a recursive function like pow and factorial

Code:

---

void recursive(int length, int x) {
  if(x > 0) {
    int i;
    for(i=0; i<length; i++) {
      recursive(length, x - 1);
    }
  }
}

---

Doesn't work at all :(

But the problem can be done using nested for loop, but as you know both of characters and maximum length are variables.

Any clue please?

Thanks in advance. :D

You'll want to print out each permutation as you go. You're handling the length OK, if x is your longest length of char's.

Now you need logic for the char increments.

I usually think of a mechanical odometer on a car. You start with all the wheels (an array) empty, and then "roll" the right most "wheel" over to the lowest letter, and just keep turning it over. When the right most wheel gets as high as it can go, then increment the wheel to it's left, and reset it to the lowest possible value letter.

[0][0]
[0][a]
[0][b]
[a][a]
[a][b]
[b][a]
[b][b]

I do this iteratively, but it can be done recursively, as well.

Wait wait...

I don't get the

Code:

---

[0][0]
[0][a]
[0][b]
[a][a]
[a][b]
[b][a]
[b][b]

---

Do you roll it like this:

Code:

---

-->
[0][0]
[0][a]
[0][b]
[a][a]
[a][b]
[b][a]
[b][b]

---

Or this:

Code:

---

[0][0]
[0][a] |
[0][b] |
[a][a] |
[a][b] v
[b][a]
[b][b]

---

Where should I begin the loop?

Or the combination of both :)
I ll try to post one solution at night, since it is kind of a handy algorithm generally

Cool! Thanks Adak! I've done it in JavaScript :D

Thank you! Thank you very much!

Quote:

---

Where should I begin the loop?

---

You always being with a "new car" odometer: All wheels set to zero (negative 1 if zero is allowed to be a value for the set of permutations.)

Now you turn the right wheel, 1 click, to get it started on it's lowest possible value:
[0][a]

Doesn't the above LOOK like the last two wheels on an odometer? :p Always the art critics, I tell ya. :)

I have code for this, but not for the recursive type. I won't post it (yet), because you'll have a blast messing with this whole concept.

Enjoy!

(No, I'm not being facetious, either - it's a blast working it out.)

Edit: Whoa! That was fast!!

Quote:

---

Originally Posted by Adak

Doesn't the above LOOK like the last two wheels on an odometer? Always the art critics, I tell ya.

---

Forgive me :D I didn't notice before.

By the way, phew,... I've done translated it into C.

Code:

---

#include <stdlib.h>
#include <stdio.h>

const char CHARS[] = { 'a', 'b', 'c' };

#define WHEEL_LENGTH      3
#define CHAR_TABLE_LENGTH (sizeof CHARS)

int wheel[WHEEL_LENGTH];

char recursiveF(int i);

void initWheel(void) {
  memset(wheel, -1, sizeof wheel);
  wheel[0] = 0;
}

void rollWheel(void) {
  while(1) {
    int i;
    for(i=0; i<WHEEL_LENGTH; i++)
      if(wheel[i] > -1)
        printf("%c", CHARS[wheel[i]]);
      else
        break;
    printf("\n");
    if(++wheel[0] >= CHAR_TABLE_LENGTH) {
      wheel[0] = 0;
      if(recursiveF(1))
        break;
    }
  }
}

char recursiveF(int i) {
  wheel[i]++;
  if(wheel[i] >= CHAR_TABLE_LENGTH) {
    wheel[i] = 0;
    if(i > WHEEL_LENGTH)
      return -1;
    return recursiveF(i + 1);
  }
  return 0;
}

int main() {
  initWheel();
  rollWheel();
  return 0;
}

---

One more time, thanks Adak! You are too handsome.

I hope you guys wanna share your algorithm or code too. Thanks.

Here's another one, but quiet ugly :D this is a modified base N counter.
Somehow, this one faster than my algorithm above.

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void wheelClick(const char *h, size_t i, size_t j) {
  size_t *a = malloc(j * sizeof(size_t));
  int b, c, d, e, f, g;
  for(b = 1; b <= j; b++) {
    c = pow(i, b);
    for(e = 0; e < c; e++) {
      d = e;
      for(f = b - 1; f > -1; f--) {
        g = pow(i, f);
        a[f] = d / g;
        printf("%c", h[a[f]]);
        d %= g;
      }
      printf("\n");
    }
  }
  free(a);
}

---

I tested both your codes. I inlined everything and anyhow made the codes be fair for testing. Uglier but fair :)

Tested for 'a','b','c','d' and length 5.
First: 1 sec and 291958 usec
Second: 0 sec and 100144 usec
Mine: 0 sec and 80115

Also note that the first code give me wrong answer for length > 4. I am counting the times you print a newline, so it might not be 100% true. I ll check it out for sure. The second is correct.

I use the same logic of the wheel. It is like having length wheels. I just don't take into acount the last wheel that changes all the time. In arr i save the character for each wheel. So length - 1.

Code:

---

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

#define length 5
#define charLen 4       

int main(){
        char arr[length-1]; int count = 0;
        const char chars[] = {'a', 'b', 'c', 'd'};
        int ok, j, k, i, line;

        for (line = 1; line <= length; ++line) {
                printf("Length: %d\n---------\n", line);
                ok = 1;
                memset(arr, 0, length - 1);
                while(ok) {
                        j = 0;
                        for (k = 0; k < charLen; ++k) {
                                for (i = line - 2; i >= 0; --i) {
                                        printf("%c", chars[(int)arr[i]]);  //print wheel
                                }
                                printf("%c\t", chars[k]);    //print last element
                        }
                        if (j != line - 1) {    //check for clicking the wheel
                        arr[j]++;
                                while (arr[j] == charLen) {
                                        arr[j] = 0;
                                        if (++j == line - 1) {ok = 0; break;}
                                        arr[j]++;                                       
                                }
                        } else {
                                ok = 0;
                        }
                }
                printf("\n\n");
        }
        return 0;
}

---

I use an array

C_ntua: Variable count is not used.