Results 1 to 8 of 8
Like Tree1Likes
  • 1 Post By JosAH

Thread: Sequence Generation

  1. #1
    otacon's Avatar
    otacon is offline Member
    Join Date
    Dec 2010
    Posts
    30
    Rep Power
    0

    Default Sequence Generation

    Hi Guys,

    I need to generate a relatively simple sequence and be able to get a next number in it, and very efficiently (it will be executed millions of times with each run)...and for some reason I'm getting stuck at finding a pretty solution. Think i'm becoming a rusty coder :(.

    To simplify: I basically need to generate a sequence of numbers, starting from say 0, which introduces a new number at a rate half time slower then a previous number..so if i start i get 0 0 the next number would be 1 --note 1 appears once exactly when a previous number (0) appeared twice now... so 0 0 1 0 0 1 2. Now that 1 appeared twice (and 0 appeared 4 times) 2 is ready to appear. So the sequence would look 0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 4 ... .

    It seems straightforward enough, but can't wrap my head around to the point that I made a long file with a handmade sequence in it and just read from that, only so I can test some things with it, but obviously in terms of efficiency that is not a acceptable solution (not to mention ugly).

    One last, but very important detail, i need to be able to generalize for different bases^2..meaning.. instead of a new number appearing with half the rate of the number-1, I might need it to to appear every 1/4 times as such: 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 2 0 0 ... Obviously if someone provides me with a nice solution or ideas for the first case, I can generalize it myself for other cases, but wanted to mention it so that you have the idea of the need for generalization in mind (instead of some nifty math trick that rely on 1/2 factor).

    Any help will be greatly appreciated!
    Last edited by otacon; 10-01-2015 at 02:06 PM.
    --Otacon
    Somebody set up us the bomb.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: Sequence Generation

    Can you post the code that you are having problems with? Be sure to wrap the code in code tags.
    Also post any output from the program that shows the problem.
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Sequence Generation

    If I write your example like this, does it help.

    Java Code:
    // 0
    // 0
    // 0   0    1
    // 0 0 1   0 0 1     2
    // 0 0 1 0 0 1 2   0 0 1 0 0 1 2     3
    // 0 0 1 0 0 1 2 0 0 1 0 0 1 2 3   0 0 1 0 0 1 2 0 0 1 0 0 1 2 3     4
    Regards,
    Jim
    Last edited by jim829; 10-01-2015 at 03:57 PM.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default Re: Sequence Generation

    Most likely it's this sequence: https://oeis.org/A215020 (bookmark that link, it's fun!)

    kind regards,

    Jos
    otacon likes this.
    Build a wall around Donald Trump; I'll pay for it.

  5. #5
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    12,059
    Rep Power
    26

    Default Re: Sequence Generation

    I don't usually post solutions, but this was fun to do with Java 8.
    Java Code:
    import java.util.HashMap;
    import java.util.Map;
    import java.util.function.IntSupplier;
    import java.util.stream.IntStream;
    
    public class SequenceSupplier implements IntSupplier {
    
      private final int base;
      private final Map<Integer, Integer> counts = new HashMap<>();
    
      public SequenceSupplier(int base) {
        this.base = base;
      }
    
      @Override
      public int getAsInt() {
        int next = 0;
        for (int i = 0; i < counts.size() + 1; i++) {
          if (counts.containsKey(i - 1) && counts.get(i - 1) == base) {
            next = i;
            break;
          }
        }
    
        if (counts.containsKey(next)) {
          counts.put(next, counts.get(next) + 1);
        } else {
          counts.put(next, 1);
        }
        
        for (int i = next - 1; i >= 0; i--) {
          counts.put(i, 0);
        }
    
        return next;
      }
    
      public void print(int limit) {
        IntStream.generate(this)
            .limit(limit)
            .forEach(i -> System.out.print(i + " "));
      }
    
      public static void main(String[] args) {
        new SequenceSupplier(2).print(200);
      }
    }
    I'm sure there must be a better / more efficient way to do this though.

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  6. #6
    otacon's Avatar
    otacon is offline Member
    Join Date
    Dec 2010
    Posts
    30
    Rep Power
    0

    Default Re: Sequence Generation

    Quote Originally Posted by JosAH View Post
    Most likely it's this sequence: https://oeis.org/A215020 (bookmark that link, it's fun!)

    kind regards,

    Jos
    Wow, that is indeed a *very* neat site!


    @DarrylBurke: Thank you! Very useful! I do think there just has to be possibly faster recursive approach, but I haven't find out it yet heh. my only working approach so far was realizing that every-time a new number is introduced the entire sequence before is repeated and appended with the new number (thanks,
    jim829) ...so I have a version that just creates a new array with double size of the one before + 1 and with correct indexing iterating through that works ..but obvious problem is the size of my array very quickly becomes too large and too slow.. and your approach seems nicer
    Last edited by otacon; 10-02-2015 at 04:07 PM.
    --Otacon
    Somebody set up us the bomb.

  7. #7
    otacon's Avatar
    otacon is offline Member
    Join Date
    Dec 2010
    Posts
    30
    Rep Power
    0

    Default Re: Sequence Generation

    Quote Originally Posted by Norm View Post
    Can you post the code that you are having problems with? Be sure to wrap the code in code tags.
    Also post any output from the program that shows the problem.
    Well, aside from the silly file loading solution I have, this also works atm...but as I mentioned earlier, its ugly and I'm afraid inefficient .

    Although, I've noticed its less inefficient than I expected, because despite exponentially growing size of the array i need to keep track of, it only needs to be rebuilt at a exponentially slower rate..which maybe doesn't make it all that horrible. (code is not generic for bigger base, but that's easily generalizable..I just wanted to see if that even works). Feedback very welcome!
    Java Code:
                    int sequence[] = {0}; // basecase
    		int nextNewInstanceID = 1; //basecase
    		int stopID = 10;	//temporary , for testing
    		int indexOffset = 0;
    		
    		
    		while (nextNewInstanceID<stopID){
    			
    			//Get new IDs in sequence
    			for(int i=indexOffset; i<sequence.length; i++){
    				System.out.println(sequence[i]);
    			}
    			
    			//Append (ugly, and only for base2 atm)
    			int sequenceNew[] = new int[2*sequence.length+1];
    			for(int i=0; i<sequence.length; i++){
    				sequenceNew[i] = sequence[i];
    			}
    			for(int i=sequence.length; i<2*sequence.length; i++){
    				sequenceNew[i] = sequence[i-sequence.length];
    			}
    			sequenceNew[sequenceNew.length-1] = nextNewInstanceID;
    			
    			
    			sequence = new int[sequenceNew.length];
    			for(int i=0; i<sequenceNew.length; i++){
    				sequence[i] = sequenceNew[i];
    			}
    			
    			//Update
    			nextNewInstanceID++;
    			indexOffset= 2*indexOffset+1;
    		}
    --Otacon
    Somebody set up us the bomb.

  8. #8
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Sequence Generation

    Here is one that appears to be a little faster. It is not as versatile as Darryl's in that the base is fixed at 2. I slightly modified one of the algorithms from Jos' Link. I also employed a bitset to keep track of even/odd counts.

    Java Code:
    class SequenceGenerator implements IntSupplier {
       BitSet counts  = new BitSet();
       int      vn      = 0;
       int      vnPlus1 = 0;
    
       public int getAsInt() {
          if (counts.get(vn)) {
             vnPlus1 = vn + 1;
          } else {
             vnPlus1 = 0;
          }
          counts.flip(vn);
          int retv = vn;
          vn = vnPlus1;
          return retv;
       }
    }
    Regards,
    Jim
    Last edited by jim829; 10-02-2015 at 09:43 PM.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Similar Threads

  1. Replies: 0
    Last Post: 01-09-2015, 11:37 AM
  2. Replies: 1
    Last Post: 01-23-2013, 06:06 PM
  3. Primary key generation in jpa : sequence type.
    By rdheepan in forum Advanced Java
    Replies: 4
    Last Post: 12-13-2011, 05:50 AM
  4. Sum sequence
    By Aero in forum New To Java
    Replies: 2
    Last Post: 09-26-2011, 06:30 PM
  5. Linked list sequence and array sequence
    By Predz in forum New To Java
    Replies: 1
    Last Post: 12-31-2009, 01:30 AM

Posting Permissions

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