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

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

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

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.

4. Re: Sequence Generation

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

kind regards,

Jos

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

6. Re: Sequence Generation

Originally Posted by JosAH
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.

7. Re: Sequence Generation

Originally Posted by Norm
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;
}```

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

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.

Posting Permissions

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