Algorithm Problem

This is a discussion on Algorithm Problem within the C Programming forums, part of the General Programming Boards category; Attention: This is absolutely not a homework By the way, I just confused about how to solve this kind of ...

  1. #1
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489

    Lightbulb [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.

    Any clue please?

    Thanks in advance.
    Last edited by audinue; 01-08-2009 at 06:03 AM. Reason: Added [SOLVED] to the title
    Just GET it OFF out my mind!!

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #3
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    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?
    Just GET it OFF out my mind!!

  4. #4
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Or the combination of both
    I ll try to post one solution at night, since it is kind of a handy algorithm generally

  5. #5
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    Cool! Thanks Adak! I've done it in JavaScript

    Thank you! Thank you very much!
    Just GET it OFF out my mind!!

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868

    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!!
    Last edited by Adak; 01-08-2009 at 03:17 AM.

  7. #7
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489

    Wink Nice day!

    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 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.
    Just GET it OFF out my mind!!

  8. #8
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    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);
    }
    Just GET it OFF out my mind!!

  9. #9
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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. #10
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    C_ntua: Variable count is not used.
    Just GET it OFF out my mind!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Dijkstra algorithm problem.
    By apacz in forum C++ Programming
    Replies: 5
    Last Post: 05-28-2005, 04:16 PM
  3. Simple algorithm problem
    By stodd04 in forum C Programming
    Replies: 11
    Last Post: 03-04-2005, 10:08 AM
  4. Algorithm question
    By PJYelton in forum C++ Programming
    Replies: 2
    Last Post: 10-28-2002, 09:52 AM
  5. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21