1. [SOLVED] Algorithm Problem

Attention: This is absolutely not a homework

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.

2. 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.

3. 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?

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

5. Cool! Thanks Adak! I've done it in JavaScript

Thank you! Thank you very much!

6. 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? 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!!

7. Nice day!

Doesn't the above LOOK like the last two wheels on an odometer? Always the art critics, I tell ya.
Forgive me 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.

8. Here's another one, but quiet ugly 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);
}```

9. 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

10. C_ntua: Variable count is not used.