1

Тема: Лексикографічне впорядкування та ArrayList

Доброго дня!

Java почав вивчати нещодавно, відповідно багато невідомого і багато проблем.
Буду вдячний, якщо хтось зможе допомогти. Власне, далі суть проблеми.

Є код для лексикографічного впорядкування масиву:

Прихований текст

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
      public static void main(String[] args) 
    {
        int myArray[] = {1,2,3};

        ArrayList<int[]> ArrayOfArrays = new ArrayList<int[]>();
        
        ArrayList<int[]> Arrays1 = new ArrayList<int[]>();
        ArrayOfArrays = Recursive(myArray, Arrays1);
        
        for (int i = 0; i < ArrayOfArrays.size(); i++)
        {
            int m[] = ArrayOfArrays.get(i); 
            for (int l = 0; l < m.length; l++)
            {
                if ((l+1) == m.length)
                {
                    System.out.println(m[l]);
                }
                else
                {
                    System.out.print(m[l] + ", ");
                }
            }        
        }

       }

    public static ArrayList Recursive(int[] myArray, ArrayList<int[]> Arrays1)
    {

    Arrays1.add(myArray);
    
           int k = myArray.length-1;
           for (int i = k; i >= 0; i--)
            {
                if (i-1 >= 0)
                {
                    if (myArray[i-1] < myArray[i])
                    {
                        int[] a = SwapArrayElements(myArray, i-1, i); 

                        Recursive(a, Arrays1);
                    }
                    
                }
                }
        return Arrays1;

    }
    
    public static int[] SwapArrayElements(int[] Array, int n1, int n2)
    {
        //Елемент n1 потрібно замінити на мінімальний елемент з хвоста (елементи після n1),
        //але такий, що є більшим за елемент n1.
        
        int a = Array[n1];
        int b = Array[n2];
        
        for (int i = n1+1; i < Array.length; i++)
        {if (Array[i] > a && Array[i] < b)
         {
         b = Array[i];
         n2 = i;
         }
        } 

        Array[n1] = b;
        Array[n2] = a;
        
        Array = ArrangeArray(Array, n1);
        
        return Array;
    }
    
    public static int[] ArrangeArray(int[] Array, int n1)
    {
    //Частину переданого масиву до елемента n1 залишаємо як є,
    //решту сортуємо в порядку зростання
    
    int newArray[];
    newArray = new int[Array.length];

    for (int i = 0; i <= n1; i++)
    {
        newArray[i] = Array[i];
        Array[i] = 0;
    }
    Arrays.sort(Array);
    
    for(int i = n1 +1 ; i < Array.length; i++)
    {
        newArray[i] = Array[i];
    }
    
    return newArray;
    }
}


Без сумніву, можна написати витонченіше та простіше. Та питання в наступному: в рекурсивній функції в Arrays1 на кожному кроці лексикографічного впорядкування додається масив (в даному випадку з трьох) чисел. Але, після виходу з рекурсії в ArrayOfArrays міститься зовсім не те, що було туди додано.

По ходу виконання додається:
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

а в кінці при переборі ArrayOfArrays виводиться

0, 0, 2
0, 1, 3
0, 0, 1
0, 1, 2
0, 0, 1
3, 2, 1

Чому так? Дякую!

2

Re: Лексикографічне впорядкування та ArrayList

На вході в функцію Recursive масив потрібно копіювати, бо інакше робота продовжується по збереженому в Arrays1 посиланні (далі всередині рекурсивної функції), змінюючи оригінальний масив вже всередині Arrays1.

Arrays1.add(Arrays.copyOf(myArray, myArray.length));

3

Re: Лексикографічне впорядкування та ArrayList

Можливо я не зрозумів чогось...але просто залишу це тут:

ArrayList<String> strings = new ArrayList<String>() {{
    add("bbccaa");
    add("abccc");
    add("aaabccc");
    add("aabbbccc");
    add("cccaaaa");
    add("ccccaaaa");
    add("dd");
}};
System.out.println(strings);

Collections.sort(strings);
System.out.println(strings);

/* output
[bbccaa, abccc, aaabccc, aabbbccc, cccaaaa, ccccaaaa, dd]
[aaabccc, aabbbccc, abccc, bbccaa, cccaaaa, ccccaaaa, dd]
*/

4

Re: Лексикографічне впорядкування та ArrayList

В мене на вході подається один масив елементів, які в процесі виконання впорядковуються використовуючи лексикографічне впорядкування, і по завершенні роботи я маю всі можливі перестановки елементів вхідного масиву (перестановки без повторень). В даному випадку - 3! варіантів.