Thread: 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.

Any clue please?

Thanks in advance.

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?

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

Thank you! Thank you very much!

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!!

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 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 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);
}

C_ntua: Variable count is not used.