Получение перестановок int [] удаления наборов дубликатов

Question

У меня есть [] целых чисел 1 <= N <= 100. Как я могу получить перестановки этого массива?-> Массив может содержать дубликаты, поэтому результирующий набор перестановок может быть дублированным, поэтому необходимо получить все неповторяющиеся перестановки.

• Я нашел много фрагментов, которые преобразуют int [] вstring и выполнять перестановки и распечатку, но поскольку i hv здесь - целые числа в диапазоне 1 <= N <= 100, то преобразование их в строку испортит целое число.</li>
• Я могу получить все перестановки с дубликатами, в том числе, для окончательного набора перестановок, где удаляются дубликаты, нужно проверить
  друг с другом, чтобы удалить дубликаты или около того, это такой тяжелый процесс.*

  Есть ли более простой способ?

  Например: 123 даст

  231
  321
  312
  132
  213
  123
  

  Аналогично для 112 программа выдаст

  121
  211
  211
  121
  112
  112
  

  Таким образом, для n-множества элементов перестановки будут иметь n!С дубликатами в элементах уменьшится, я спрашиваю, как я могу удалить эти дубликаты наборов.(дубликат набора перестановок arr [])

Answer 1

Если допустимо сначала отсортировать элементы лексически, то вы можете выполнить свою лексическую перестановку.Включая алгоритм, который делает это для массива int, легко модифицируемого для строк.

public static boolean permuteLexically(int[] data) {
    int k = data.length - 2;
    while (data[k] >= data[k + 1]) {
        k--;
        if (k < 0) {
            return false;
        }
    }
    int l = data.length - 1;
    while (data[k] >= data[l]) {
        l--;
    }
    swap(data, k, l);
    int length = data.length - (k + 1);
    for (int i = 0; i < length / 2; i++) {
        swap(data, k + 1 + i, data.length - i - 1);
    }
    return true;
}

Пример использования

public static void main(String[] args) {
    int[] data = { 1,2,3 };
    do {
        System.err.println(Arrays.toString(data));
    } while(Util.permuteLexically(data));
}

Использование с [1,2,3] вы получаете

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

с [1,1,3] вместо этого вы получаете

[1, 1, 3]
[1, 3, 1]
[3, 1, 1]

, что, как я думаю, вы просили.

Так как метод«переставляет» следующую перестановку в лексикографическом порядке, важно, чтобы элементы были упорядочены.Начиная с [3, 2, 1] вы больше не получите перестановок (сравните с примером выше).

Answer 2

Вы можете использовать Set вместо массива дюймов , это может автоматически удалить ваши дубликаты.

Редактировать: @allingeek дай мне идею.Более чем реализуя свой собственный Set , вы можете написать обертку над int и переписать ваши методы equals и hashcode, найдя способ, в котором ваши перестановки равны.Возможно использование чисел по порядку и другие рекомендации, приведенные в «Эффективной Java» (для реализаций equals и hashcode, чтобы избежать ошибок).Это может дать вам лучший способ найти ваши перестановки в наборе .Больше, чем использовать язык выражений, как я говорю сначала.

Answer 3

Требуются все неповторяющиеся перестановки массива. Их число, при условии, что каждая запись массива уникальна, Factorial (array.length), быстро становится неисчислимо большим. Но при условии, что вы хотите перечислить их, проще всего сделать следующее:

Ваша проблема - в основном проблема выбора по вашему алфавиту (1 <= N <= 100). Не имеет значения, хотите ли вы выбрать 5 из этих или 500, вы хотите выбрать какой-то номер, позвоните ему, х. Подумайте об уникальных элементах, которые вы хотите выбрать, о тех, которые вы не хотите дублировать (это может быть правильным подмножеством вашего алфавита или нет). Разложите эти элементы в ряд. Длина этого ряда равна n. Теперь проблема выбора перечисления x из них может быть решена следующим образом. Подумайте о n-битном числе, которое может содержать только n-x нулей. Чтобы получить это число ранга-x, просто начните с 0 и перечислите все возможные числа до 2 ** n, выбирая только те, которые имеют ровно x 1s (и n-x нули). Эти 1 затем выбирают x позиций из n позиций вашего алфавита, и каждое из этих чисел ранг-x выбирает для вас перестановку. </p>

Если кто-то знает оптимизацию, чтобы вам не приходилось работать со всеми не рангами-х, скажите, пожалуйста. РЕДАКТИРОВАТЬ: Ответ, похоже, здесь

Answer 4

1. Сортировка массива.
2. Использование вложенного цикла, в котором внешний цикл выполняет итерацию по каждому элементу в массиве.Если следующий элемент имеет то же значение, что и последний, пропустите.Затем внутренний цикл помещает этот элемент в каждую позицию в списке.Сохранение перестановки в каждом цикле.

Это будет генерировать перестановки, а также пропускать повторяющиеся перестановки.

int[] sortedSourceArray = ...;
int last = -1;
int current = -1;
// build one permutation with the original array
buildPermutation(permutationList, sortedSourceArray);  // I'm not going to implement this for you.
for (int i = 0; i < sortedSourceArray.length; i++) {
  current = sortedSourceArray[i];
  // check if the new value is the same as the last
  if(current == last) 
    continue;
  // remove the current element from the list
  // build your permutations
  for(int j = 0; j < sortedSourceArray.length; j++) {
    // skip if its inserting the element at its original position
    if(j == i)
      continue;
    // fix the duplicates for blocks of repeated elements
    if(j < sortedSourceArray.length-1 && sortedSourceArray[j+1] == current)
      continue;
    // inject the current element at the new position
    inject(sortedSourceArray, current, j); 
    // build the permutation
    buildPermutation(permutationList, sortedSourceArray);
    // remove the current element from that position
    remove(sortedSourceArray, j);
  }
  last = current;
}

РЕДАКТИРОВАТЬ: На самом деле я думаю, что это должно быть немного подправленобольше, чтобы захватить последние несколько случаев, когда генерируются дубликаты.Это было бы, где повторный элемент вставлен рядом с его тем же значением.Я изменил код соответствующим образом.

Answer 5

Самый простой способ удалить дублирующиеся элементы - добавить содержимое в Set, который не допускает дублирование, а затем добавить Set обратно к ArrayList какпример ниже.

ArrayList<String>al=new ArrayList<String>();

al.add(String.valueOf(arr[0]));  //Just as an example.

HashSet hs = new HashSet();
hs.addAll(al);
al.clear();
al.addAll(hs);