Using an array of arrays (int[][]), create a method to find all cycles within a given permutation [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

So I can just use standard arrays for this, nothing else. I have to find a way to make a method that finds all the cycles in the given permutation and returns them as an array object of arrays. Then I have to place the lowest of each array as the first entry of the array. Then sort them by lowest.

I can't use arraylists or sets or anything.

EDIT: By cycles I mean take the integer value of the initial object and locate the index value that it corresponds to. Take that integer value at that index and do the same. Continue doing this until it points back to an object that's already been referenced.

An example: [0, 4, 2, 8, 7, 9, 1, 6, 5, 3]

would be these cycles : [0] [4, 8, 5, 7, 6, 9, 3, 2] [1]

and return this: [0], [1], [2, 4, 8, 5, 7, 6, 9, 3]

or

This array: [2, 4, 8, 1, 5, 3, 9, 0, 7, 6]

would be these cycles : [2, 8, 7, 0] [4, 5, 3, 1] [9, 6]

and return this : [0, 2, 8, 7], [1, 4, 5, 3], [6, 9]

I am so lost, any help would be wonderful. thanks ahead of time!

Answer 1

Don't ask why I took the time to do this.

EDIT: Totally working now

public class Main {

    public Main()
    {

    }

    public static void main(String[] args)
    {
        int array[] = {0, 4, 2, 8, 7, 9, 1, 6, 5, 3};
        Main m = new Main();
        int[][] cycles = m.getCycles(array);
        for (int i = 0; i < cycles.length; i++)
        {
            System.out.print("[");
            for (int j = 0; j < cycles[i].length; j++)
            {
                System.out.print(cycles[i][j]);
                if (j < cycles[i].length - 1)
                    System.out.print(", ");
            }
            System.out.println("]");
        }
        System.out.println("end debug");
    }

    public int[][] getCycles(int[] array)
    {
        int[][] cycles = new int[array.length][array.length];

        // initialize the cycles to all -1s, cuz they'll never be in the array
        for (int i = 0; i < cycles.length; i++)
        {
            for (int j = 0; j < cycles[i].length; j++)
            {
                cycles[i][j] = -1;
            }
        }

        int i = 0;

        do {
            int nextElement = array[i];

            int j = 0;
            do {
                cycles[i][j] = nextElement;
                nextElement = array[nextElement];
                j++;
            } while (!elementInArray(cycles[i], nextElement) && j < array.length);


            i++;
        }  while (!arrayHasCycled(array, cycles) && i < array.length);


        cycles = removeNegativeOnes(cycles, i);

        for (i = 0; i < cycles.length; i++)
        {
            pushForward(cycles[i]);
        }

        return cycles;
    }

    public boolean elementInArray(int[] array, int element)
    {
        for (int i = 0; i < array.length; i++)
        {
            if( array[i] == element)
                return true;
        }

        return false;
    }

    public int[][] removeNegativeOnes(int[][] cycles, int numCycles)
    {
        int [][] newCycles = new int[numCycles][];
        for (int i = 0; i < numCycles; i++)
        {
            int realLenOfCycle = indexOf(-1, cycles[i]);
            newCycles[i] =  new int[realLenOfCycle];
            for (int j = 0; j < newCycles[i].length; j++)
            {
                newCycles[i][j] = cycles[i][j];
            }
        }

        return  newCycles;
    }

    public int indexOf(int element, int[] array)
    {
        int index =  -1;

        for (int i = 0; i < array.length; i++)
        {
            if (array[i] == element)
                return i;
        }

        return index;
    }

    public boolean arrayHasCycled(int[] array, int[][] cycles)
    {
        for (int i = 0; i < array.length; i++)
        {
            boolean cycleHasValue = false;
            for (int j = 0; j < cycles.length; j++)
            {
                for (int k = 0; k < cycles[j].length; k++)
                {
                    if (cycles[j][k] == array[i])
                        cycleHasValue = true;
                }
            }
            if (!cycleHasValue)
                return false;
        }

        return true;
    }

    public void pushForward(int [] array)
    {
        int lastElement = array[array.length - 1];
        for (int i = array.length - 1; i > 0; i--)
        {
            array[i] = array[i - 1];
        }

        array[0] = lastElement;
    }
}

Output:

[0]
[1, 4, 7, 6]
[2]
[3, 8, 5, 9]

From what I understand, you're asked us to create a code which executes the following algorithm:

1. Create a one-dimensional array of integers, array
2. For each element in that array, nextElement do the following:
3. Create a new one-dimensional array, currCycle that will be added to a two-dimensional array, cycles.
4. Set the first element of that array to nextElement.
5. nextElement then becomes array[nextElement]
6. If nextElement is already in currCycle, continue onto the next element of array
7. Check if all the elements of array are in cycles, and if so, stop executing this algorithm.
8. Finally, return the cycles as a two-dimensional array with the index that was being used instead of the element at that index, which is what the current array consists of. To accomplish this, just cyclically (in the normal sense) push each element of the array forward one index.

This doesn't follow your examples exactly, but I think you may have malformed your examples, for instance:

An example: [0, 4, 2, 8, 7, 9, 1, 6, 5, 3]

would be these cycles : [0] [4, 8, 5, 7, 6, 9, 3, 2] [1]

and return this: [0], [1], [2, 4, 8, 5, 7, 6, 9, 3]

The first element 0 is 0, so when you get 0, it's already in the current cycle, so go to the next element, the element at index 1, which is 4. Once you're at 4 go to the fourth element, which is 7 not 8!

 0  1  2  3  4
[0, 4, 2, 8, 7...