Thread: arraylist keeps reseting initial value?

Hi everybody, I have to write a program that enumerates all possible walks of any number of random 1 dimensional steps, and I think I have everything right, except my arraylist that I use to keep track of walks and compare further ones to keeps resetting the initial steps array that I gave it and I cant figure out why. Ive been working on this for hours and cant figure out why it does that. Any help is much appreciated!

import java.util.*;
 
public class WalkAvgEnum {
 
    public static void main(String[] args) {
        int N = 2;
        int pos = 0;
        int count = 0;
        int lastpos = pos;
        double all = Math.pow(2.0, (double) N);
        ArrayList<int[]> steps = new ArrayList<int[]>();
        int[] xAccum = new int[(int) all];
        int[] xSq = new int[(int) all];
        boolean samesnew[] = new boolean[(int) all];
        boolean sames[][] = new boolean[(int) all][N];
        boolean same = false;
        boolean first = true;
        int[] test = new int[N];
        for(int m=0; m<samesnew.length; m++)
            samesnew[m] = true;
        for(int m=0; m<sames.length; m++)
            for(int l=0; l<sames[m].length; l++)
                sames[m][l] = false;
        while (steps.size() < all) {
            System.out.println(steps.size());
            for(int i=0; i<N; i++) {
                double p = Math.random();
                System.out.println(p);
                if(p < .5) {
                    pos--;
                    test[i] = pos;
                }
                else {
                    pos++;
                    test[i] = pos;
                }
                System.out.println(test[i]);
            }
            if(steps.size() == 1)
                System.out.println(steps.get(0)[0]);
            if (count==0 && first==true) {
                steps.add(test);
                xAccum[count] = pos;
                xSq[count] = pos*pos;
                count++;
                pos = 0;
                first = false;
                for(int i=0; i<N; i++) {
                    System.out.println(test[i]);
                }
            }
 
            else {
                for(int j=0; j<count; j++) {
                    for(int k=0; k<N; k++) {
                        if(test[k]!=steps.get(j)[k])
                            samesnew[j] = false;               //never false because steps.get(j) changes its value to test although I dont know why
 
                        System.out.println(steps.get(j)[k]);
                        System.out.println(test[k]);
                    }
                    System.out.println(sames[j]);
                }
 
 
                for(int m=0; m<count; m++){
                    System.out.println(samesnew[m]);
                    if(samesnew[m] == true)
                        same = true;
                }
                if(same != true) {
                    steps.add(test);
                    xAccum[count] = pos;
                    xSq[count] = pos*pos;
                    count++;
                }
            }
            for(int m=0; m<samesnew.length; m++)
                samesnew[m] = true;
            System.out.println(steps.get(0)[1]);
            pos = 0;
            same = false;
            for(int m=0; m<sames.length; m++)
                for(int l=0; l<sames[m].length; l++)
                    sames[m][l] = false;
 
        }
        System.out.println();
        for(int i=0; i<(int) all; i++)
            System.out.println(xAccum[i]);
 
    }
 
}

Welcome to the forum.

Please read this topic to learn how to post code in code or highlight tags and other useful info for newcomers.

ok I made the code readable now, I just dont understand why the arraylist would keep changing its first value when I never tell to :/

Can you give an example of what you mean by "changing its first value?" Can you show a sample output or what you're seeing in the code or output that is causing you to say that the value is changing? I'm not sure what you mean.

0
0.13535019992237296
-1
0.03138735803814374
-2
-1 steps.get(0)[0] initially
-2
-2 steps.get(0)[1] initially
1
0.6373879863545836
1
0.7248267662748011
2
1
1 steps.get(0)[0] value changes
1
2 steps.get(0)[1] value changes
2
[Z@5e1387c6
true
2
1
0.6498893050834869
1
0.40505736508081025
0
1
1 value changes
1
0 value changes
steps.get(0) keeps getting modified for some reason

Your code is very confusing and hard to follow, some comments would be helpful, but I think you'll find that the value of steps.get(0)[0] is always the same as test[0]. So the value you're asking about changes, because the value of test[0] changes.

so what if i used a 2 dimensional array instead of an arraylist, would a value of a new array steps[0][0] change because test[0] changes?

If the new 2D array still contains the test array as its first row, then yes, the values will still be the same.

Can you describe what you're trying to do? Maybe there's an easier or better way I can suggest you try. What does "a program that enumerates all possible walks of any number of random 1 dimensional steps" mean? Can you give a simple example?

If an object randomly steps twice in one dimension, there are four possibilities of the different paths it can take. With 0 being the start position, it can move to -1 to 0, 1 to 0, -1 to -2, or 1 to 2. What Im interested in is finding all possible end positions of the object for a given number of steps and the frequencies with which they occur, so I want for 2 steps i want -2, 0, 0, and 2, for 3 I want the 8 possible positions where it can end at, and so on.

It's interesting you already know that there are 8 possible endings for 3 steps. I assume the 8 endings are not unique endings but there are unique paths to get to those 8 endings.

So think of the problem as a tree where each ending position has 2 possible branches to the next ending. All paths start with 0. From 0 there are two possible moves, -1 and 1. The 2 possible moves from each of those endings: from -1, the possible moves are -2 and 0. From 1, the possible moves are 2 and 0. So after 2 steps, the endings are -2, 0, 0, and 2. Find all moves from those endings:

-2: -3, -1
0: -1, 1
0: -1, 1
2: 1, 3

and you have all endings for 3 steps. The next possible moves from each of those 8 endings gives the endings for 4 steps and so on. Already we see that the number of endings for number of steps n is 2^n.

How to program that? If you draw it out, it looks something like:

                0
             /     \ 
           -1       1
         /   \     /  \
       -2    0    0    2
      /  \  / \  / \  / \
    -3  -1 -1 1 -1 1  1 3

What you know: Each group of endings builds on the previous, the number of endings can be calculated from the number of steps. An approach might be to find the number of endings for m steps by building the endings for each number of steps n < m, beginning with n = 1.

Edit: Staring at it a bit more and writing out the 4 step endings, I see there's a shortcut to finding the endings and the frequency of each ending for the next step from the previous step's results. I don't yet see the algorithm for finding the endings and their frequency for any number of steps without having the previous step's results, but I think it's possible and might even be fairly simple.

Any progress?

Staring at it a bit longer, I see the possible endings and their frequency can be diagrammed with a pyramid, like this:

                         Frequency of each ending
Steps   Endings -/+  8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8
  0         1                        1
  1         2                      1   1
  2         4                    1   2   1
  3         8                  1   3   3   1
  4        16                1   4   6   4   1
  5        32              1   5   10  10  5   1
  6        64            1   6   15  20  15  6   1
  7       128          1   7   21  35  35  21  7   1
  8       256        1   8   28  56  70  56  28  8   1

It's easy to see from the pyramid how the next result can be derived from the current result. The brute force method (start with the 1-step case and derive each of the following cases until the desired number of steps is reached) can be programmed with nested for loops, 2 loops total.

yup I found a way to do it with queues! and wow that pretty interesting to see that it can be diagrammed like that. Thanks for all your help though!

Queues. That's interesting. Here's the important part of my nested for loop solution:

// find all unique ending values and populate an array that contains the
// frequency of occurrence of each unique ending
private int[] calculateEndingFrequency( int numberOfSteps )
{
    // the number of unique endings is 1 more than the number of steps
    int[] stepFrequency = new int[numberOfSteps + 1];
    // initialize the frequency array for the zero-step case
    stepFrequency[0] = 1;
 
    // for numberOfSteps = 0, return the current result
    if ( numberOfSteps == 0 )
    {
        return stepFrequency;
    }
 
    // continue initialization of the array for the single step result
    // this is the first term of the second row of the pyramid
    stepFrequency[1] = 1;
 
    // calculate each array by finishing the single step result (row 2 of
    // the pyramid) to the specified number of steps (row numberOfSteps + 1
    // of the pyramid)
    for ( int i = 2 ; i <= numberOfSteps ; i++ )
    {
        // each pass through the for loop expands the current array. the
        // expansion begins by setting the next zero element to 1
        stepFrequency[i] = 1;
 
        // a temporary array contains a copy of the current array and is
        // used to calculate the next iteration of the stepFrequency array
        int[] tempArray = Arrays.copyOf( stepFrequency, stepFrequency.length );
 
        // calculate the current array's values between the first and last
        // non-zero elements by adding the elements in the temp array
        // (see the diagram above to understand how adding elements of
        //  previous array builds the next array)
        for ( int j = 1 ; j < i ; j++ )
        {
            // set the jth element of the current array equal to the sum
            // of elements in the preceding row to the left and to the
            // right of the current element
            stepFrequency[j] = tempArray[j - 1] + tempArray[j];
        }
    }
 
    return stepFrequency;
 
} // end method calculateEndingFrequency()