k-перестановка элементов в ArrayList Java

Question

Я искал простой метод для получения k-перестановки элементов в одном ArrayList.

У меня есть arrayList объектов X, и я хочу получить все возможные перестановки (количество порядков)элементы, основанные на значении k.

Пока что я нашел только комбинации и перестановки всех элементов (в основном целочисленные значения), но не нашел решения k-перестановок объектов в списке массивов.

Может кто-нибудь мне помочь?

Пока я нашел это, но я не знаю, как приспособиться к моему делу:

 public static void perm2(String s, int k)
    {
    perm2("", s, k);
    }
    public static void perm2(String prefix, String s, int k)
    {
    int N = prefix.length();

    int M = s.length();

    if(N == k) System.out.println(prefix);
    else
        {
        for(int i = 0; i < M; i++)
            perm2(prefix+s.charAt(i), s.substring(0, i) + s.substring(i+1, M), k);
        }
    }
    public static void main(String[] args)
    {
    String alphabet = "123";
    int N = alphabet.length();
    int K = 2;
    String elements = alphabet.substring(0, N);
    perm2(elements, K);
    }

Answer 1

Насколько я понимаю, вы хотите сгенерировать все перестановки k элементов из List длины n, где n >= k.

static <E> void permK(List<E> p, int i, int k)
{
  if(i == k)
  {
    System.out.println(p.subList(0, k));
    return;
  }

  for(int j=i; j<p.size(); j++)
  {
    Collections.swap(p, i, j);
    permK(p, i+1, k);    
    Collections.swap(p, i, j);
  }
}

Тест:

public static void main(String[] args)
{
  permK(new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)), 0, 3);
}

Выход:

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 2]
[1, 3, 4]
[1, 3, 5]
[1, 4, 3]
[1, 4, 2]
[1, 4, 5]
[1, 5, 3]
<snip>
[5, 3, 1]
[5, 4, 3]
[5, 4, 2]
[5, 4, 1]
[5, 1, 3]
[5, 1, 4]
[5, 1, 2]

Answer 2

Ну, много слов.Согласно заголовку, вы хотите получить k-th упорядоченную перестановку заданного массива.

Пример.

• начальный массив: abcde
• 0th : abcde
• 1st : abced
• last : edcba
• youнужно найти kth перестановку

У вас есть два способа ее решения:

1. Внедрить лексикографическую сортировку вручную и выполнить итерацию по k-й перестановке.Требуется O (n) время;
2. Вы можете использовать Факториальные системы счисления , что позволяет решить эту проблему за O (1) время.