Блог

Главная - Вопросы по программированию - Необходимо печатать уникальные комбинации чисел из массива при повторении элементов

Необходимо печатать уникальные комбинации чисел из массива при повторении элементов

#java

#ява #java

Вопрос:

Мне нужно написать программу, где я буду печатать уникальные комбинации чисел из массива. Пример: Ввод {1,2,1} вывод должен быть: 121,112,211 Я пробовал приведенный ниже код, но он возвращает только 1 комбинацию. Также это должен быть стандартный ввод.

  import java.util.ArrayDeque;
import java.util.Deque;

class Main
{
     static void combinationUtil(int arr[], int data[], int start, 
                                int end, int index, int r) 
    { 
        // Current combination is ready to be printed, print it 
        if (index == r) 
        { 
            for (int j=0; j<r; j  ) 
                System.out.print(data[j] " "); 
            System.out.println(""); 
            return; 
        } 
   
        for (int i=start; i<=end amp;amp; end-i 1 >= r-index; i  ) 
        { 
            data[index] = arr[i]; 
            combinationUtil(arr, data, i 1, end, index 1, r); 
        } 
    } 
  
    static void printCombination(int arr[], int n, int r) 
    { 
   
        int data[]=new int[r]; 
  
        combinationUtil(arr, data, 0, n-1, 0, r); 
    } 
 
    public static void main (String[] args) {  
int r=3;
        Scanner input = new Scanner(System.in);
        System.out.println("How many numbers do you want to enter?");
        int num = input.nextInt();

        int arr[] = new int[num];

        System.out.println("Enter the "   num   " numbers now.");

        for (int i = 0 ; i < arr.length; i   ) {
            arr[i] = input.nextInt();
        }
        input.close(); 
        int n = arr.length; 
        printCombination(arr, n, r); 
    } 
}

Комментарии:

1. Это не вопрос домашней работы.

2. Я вижу, что вы объявляете r , но не инициализируете его. Не уверен, что это сделано намеренно, но почти уверен, что это одна из причин поведения, которое вы видите. Кроме того, вы return из combinationUtil() после печати текущей комбинации. Учитывая, что вы передаете методу index значение 0, а r по умолчанию инициализируется значением 0, но никогда не изменяется, тогда код выполняет именно то, что он предназначен для выполнения: печать текущей комбинации.

3. @JustAnotherDeveloper , да, сейчас я инициализирую r до 3, но результат все тот же:(

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

Ответ №1:

Эта задача вызывает перестановку. Вам нужно найти все перестановки заданных чисел.

 public static void main(String[] args) {
    System.out.println(permute(1, 2, 1));   // [[2, 1, 1], [1, 1, 2], [1, 2, 1]]
}

public static Set<String> permute(int... nums) {
    if (nums == null || nums.length == 0)
        return Collections.emptySet();

    Arrays.sort(nums);
    return permute(new HashSet<>(), nums, -1);
}

private static Set<String> permute(Set<String> res, int[] nums, int j) {
    j  ;

    if (j == nums.length - 1)
        res.add(Arrays.toString(nums));
    else {
        for (int i = j; i < nums.length; i  ) {
            swap(nums, j, i);
            permute(res, nums, j);
            swap(nums, j, i);
        }
    }

    return res;
}

private static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Комментарии:

1. Это имеет смысл, попробую.