Detecting repeating patterns in cycles.. Please Help!
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Detecting repeating patterns in cycles.. Please Help!

  1. #1
    Join Date
    Oct 2008
    Posts
    8

    Exclamation Detecting repeating patterns in cycles.. Please Help!

    Hi,
    I'm trying to find a way to detect for repeating patterns in my cycle...but I'm not quite sure how.

    My program repreats the procedure of:
    given an input, remove the first 3 characters, and then add characters at the end of the string (if 1 add 1101, if 0 add 00). Now repeat the same on the result string.

    It runs out and stops if the string to be processed becomes less than 3 characters. It shoudl also be able to detect infinite loops --though I'm not exactly sure how to do this, for now I'm making it run for 1000 iterations before stopping and calling it an infinite loop.... if there are any suggestions on this, that would be much appreciated.

    The main problem is now, to be able to detect repeating patterns in the cycle.
    E.g. given the input 1101, if I do the procedure, the result will be:
    Input: [1, 1, 0, 1]
    removed list: [1]
    added list: [1, 1, 1, 0, 1]
    removed list: [0, 1]
    added list: [0, 1, 1, 1, 0, 1]
    removed list: [1, 0, 1]
    added list: [1, 0, 1, 0, 0]------------------
    removed list: [0, 0]
    added list: [0, 0, 1, 1, 0, 1]xxxxxxxxxxxxxx
    removed list: [1, 0, 1]
    added list: [1, 0, 1, 0, 0]-------------------
    removed list: [0, 0]
    added list: [0, 0, 1, 1, 0, 1]xxxxxxxxxxxxxxxx
    removed list: [1, 0, 1]
    added list: [1, 0, 1, 0, 0]-------------------
    removed list: [0, 0]

    from the marked lines we can see a repeating pattern. I can visibly detect the repition, but how can I make my program do it...???

    so far the code for main method important in doing the procedure is:

    Code:
    public ArrayList<String> processString(ArrayList<String> userInput, ArrayList<String> rules, int loop){
    	char[] separatedChar;
    	String converted;
    
    	if (loop==0){System.out.print("infinite loop");System.exit(0);}
    	int howmany = 3;
    	
    	if(userInput.size()< howmany){
    		System.out.print("Stopped because [] contains " +
    				"fewer characters than need to be removed ");
    		System.exit(0);
    	}
    	if ((userInput.get(0)).equals(rules.get(0))){
    		//if user input is 0 (which is what you get fromrules.get(0))
    		//remove the how many ever characters specified from the front of the list(3 in this case)
    		//chars from the front of the list
    		int int1 = Integer.parseInt(rules.get(1));
    		for(int j=0; j<int1; j++){
    		userInput.remove(0);
    		}
    		System.out.println("removed list: " + userInput);
    		//if user input is 0
    		//(e.g. [00] to [0,0])by converting to CharArray and then reconverting 
    		//it to String.
    		String toAdd =rules.get(2);
    		separatedChar = toAdd.toCharArray();
    		
    		for(int j=0; j<separatedChar.length; j++){
    			converted = Character.toString(separatedChar[j]);
    			userInput.add(converted);
    			}
    		System.out.println("added list: " + userInput);
    		
    		}
    	
    	if ((userInput.get(0)).equals(rules.get(3))){
    		//if user input is 1
    		//remove the how many ever characters specified from the front of the list
    		//chars from the front of the list
    		int int2 = Integer.parseInt(rules.get(4));
    		for(int j=0; j<int2; j++){
    		userInput.remove(0);
    		}
    		System.out.println("removed list: " + userInput);
    		
    		//beforeuserInputg the rule to UserInput, separates the String 
    		//(e.g. [1101] to [1,1,0,1])by converting to CharArray and then  
    		//reconverting it to String.
    		String toAdd =rules.get(5);
    		separatedChar = toAdd.toCharArray();
    		
    		for(int i=0; i<separatedChar.length; i++){
    		converted = Character.toString(separatedChar[i]);
    		userInput.add(converted);
    		}
    		System.out.println("added list: " + userInput);
    		detectCycle(userInput);
    	}
    	loop--;	
    	return processString(userInput, rules, loop);
    	
    }
    Any help would be very much appreciated....

    Thankyou in advance.
    Last edited by kingfisher; October 20th, 2008 at 05:10 AM.

  2. #2
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

    Re: Detecting repeating patterns in cycles.. Please Help!

    How, exactly, do you define a repeating pattern in this context? 1, 1, 1 is a repeating pattern of 1s, 0, 0 is a repeating pattern of 0s...

    As far a infinite loops go, I suspect you'll need to decide in advance which sequences can result in a infinite loop and then detect them in the code.

    First, solve the problem. Then, write the code...
    John Johnson
    Please use &#91;CODE]...your code here...&#91;/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

  3. #3
    Join Date
    Jun 1999
    Location
    SW Missouri
    Posts
    3,430

    Re: Detecting repeating patterns in cycles.. Please Help!

    "I can visibly detect the repition,"
    If you can explain how you do that, you can write the code.
    Norm

  4. #4
    Join Date
    Oct 2008
    Posts
    8

    Re: Detecting repeating patterns in cycles.. Please Help!

    Quote Originally Posted by dlorde
    How, exactly, do you define a repeating pattern in this context? 1, 1, 1 is a repeating pattern of 1s, 0, 0 is a repeating pattern of 0s...
    by the repreating pattern I mean that when I do the procedure on the input and its consequent result -at one point, it starts to form a cycle in which the same values result over and over again.
    1101
    - - -11101
    - - - - - -011101
    - - - - - - - - - 10100
    - - - - - - - - - - - -001101 (from this point onwards, the same values keep
    - - - - - - - - - - - - - - -10100 appearing alternatively -thats the
    - - - - - - - - - - - - - - - - - -001101 repeating pattern)
    - - - - - - - - - - - - - - - - - - - - -10100 etc.

    Quote Originally Posted by dlorde
    As far a infinite loops go, I suspect you'll need to decide in advance which sequences can result in a infinite loop and then detect them in the code.
    its not exactly determinable I think.. there are too many possibilities... because it depends on whatever string the user inputs...
    Or maybe I'm not understanding your statement correctly.. could you be a little more specific? Thanks.

    And Norm,
    well I sort of look at the output and then search for repeating patterns...So I was thinking of maybe implementing a linkedlist and after determining each "added list" searching through the linkedlist to find any matching inputs, and if not adding it to the linkedlist. And if it does match then we determine whether the next "added list" produced will match the next entry from that linkedList....but then I don't know how long this needs to be kept running before determining that it is a cycle...because the cycle may be as long 10 entries and return back to it...
    Somehow I think my apprach is not quite feasable...I'm not able to work out the logic of it clearly...
    Any help? or any better ideas?

  5. #5
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

    Re: Detecting repeating patterns in cycles.. Please Help!

    Quote Originally Posted by kingfisher
    by the repreating pattern I mean that when I do the procedure on the input and its consequent result -at one point, it starts to form a cycle in which the same values result over and over again.
    1101
    - - -11101
    - - - - - -011101
    - - - - - - - - - 10100
    - - - - - - - - - - - -001101 (from this point onwards, the same values keep
    - - - - - - - - - - - - - - -10100 appearing alternatively -thats the
    - - - - - - - - - - - - - - - - - -001101 repeating pattern)
    - - - - - - - - - - - - - - - - - - - - -10100 etc.
    OK, look like you need to keep a record of the previously generated values and compare each newly generated one with the previous values.

    its not exactly determinable I think.. there are too many possibilities...
    If it's not determinable, then you won't be able to do it. That's what non-determinable means. I would hazard a guess that there must be some determinable property common to all inputs that will cause infinite loops. Otherwise why has the question been asked?

    The Difficult is that which can be done immediately; the Impossible that which takes a little longer...
    George Santayana

    Nothing is impossible for the person who doesn't have to do the work...
    Anon
    Please use &#91;CODE]...your code here...&#91;/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

  6. #6
    Join Date
    Oct 2008
    Posts
    8

    Re: Detecting repeating patterns in cycles.. Please Help!

    Quote Originally Posted by dlorde
    OK, look like you need to keep a record of the previously generated values and compare each newly generated one with the previous values.
    Yeah thanks, I store in each output in a different ArrayList and check whether it has already occured.

    If it's not determinable, then you won't be able to do it. That's what non-determinable means. I would hazard a guess that there must be some determinable property common to all inputs that will cause infinite loops. Otherwise why has the question been asked?
    Well it was part of an assignment...so I dont know 'why' its been asked...
    But I just kept it as doing 1000 iterations and then deeming it infinite, and terminating the procedure.

  7. #7
    dlorde is offline Elite Member Power Poster
    Join Date
    Aug 1999
    Location
    UK
    Posts
    10,163

    Re: Detecting repeating patterns in cycles.. Please Help!

    Quote Originally Posted by kingfisher
    But I just kept it as doing 1000 iterations and then deeming it infinite, and terminating the procedure.
    OK, that's a decent pragmatic approach - for values of infinity greater than 1000 I think I'd probably accept that as an answer.

    Everything should be made as simple as possible, but not simpler...
    A. Einstein
    Please use &#91;CODE]...your code here...&#91;/CODE] tags when posting code. If you get an error, please post the full error message and stack trace, if present.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center