0

A state is a list of random integers from 0 - 4. Example = [1, 0, 2, 3, 2]. A neighbour is described as a change in one of the integers in the list. For example [0, 0, 2, 3, 2] is a neighbour of [1, 0, 2, 3, 2]. How would I find all possible neighbours of a given state?

wjandrea
  • 28,235
  • 9
  • 60
  • 81
M. Petras
  • 1
  • 1
  • 2
    Some kind of loop, I would guess. What have you tried, and what's stopping you from proceeding? – jez Oct 14 '19 at 18:19
  • 1
    If the difference between a state and its neighbour is exactly one integer, then you won't be able to list _all_ the neighbours since there will be infinitely many of them: `[2, 0, 2, 3, 2]`, `[3, 0, 2, 3, 2]` and so on would also be neighbours – ForceBru Oct 14 '19 at 18:24
  • This could be helpful: [compute list difference](https://stackoverflow.com/q/6486450/4518341). Order matters, right? Once you have the difference, you would just need to get its `len`. – wjandrea Oct 14 '19 at 18:25
  • Oops, I misunderstood the question. I thought you would get two lists and have to determine if they're neighbors. – wjandrea Oct 14 '19 at 18:52

1 Answers1

0

You can find the total number of permutations for your sequence by using the formula n^r where n is the number of numbers you use and r is the number of elements in your sequence. In your case this would be 5^5. You can read more about this and see all the possible permutations here.

From the list you can create from what we've just calculated you can determine which of these permutations are neighbors and keep a count of each one you encounter. You can do this using a for loop (for each permutation, check if it's a neighbor).

I have added a method I made called isNeighbor which returns true or false depending. Although this is in java the same prinicples I use also apply in python. I hope you are still be able to follow it with the comments I've supplied. If not I can try and explain further.

int[] cell = {1,0,2,3,1}; 
int[] cell = {0,0,2,3,1}; //example cells (stored as array of integers)

static boolean isNeighbor(int[] cell, int [] cell2)
    {
        int count = 0;
        for(int i = 0; i < cell.length;i++) //for each number in array
            if(!(cell[i] == cell2[i])) //if the number at the same index isn't the same
                if(Math.abs(cell[i] - cell2[i]) != 1) //if the difference isn't 1
                    count+=2;
                else
                    count++;
        if(count > 1)
            return false; // is not a neighbor
        else
            return true; // is a neighbor
    }

If you need any clarification regarding this method or where to go from here feel free to ask! :)

Edd
  • 136
  • 9