Комбинации всех возможных элементов массива

@Zelmm · Регистрация: 20.07.2016

Студворк — интернет-сервис помощи студентам

Добрый день форумчане.
Есть такая задачка, как реализовать комбинацию всех возможных элементов массива, на пример имеем массив из 3 элементов:

Java
1
int [] array = {1, 2, 3};

Просто комбинацию всех элементов массива я получил и это в данном случае это 6 элементов:

123; 132; 213; 231; 312; 321

Теперь вопрос, как можно реализовать алгоритм, который в данный список комбинаций добавляет так же и вот эти:
12; 13; 21; 23; 31; 32; 1; 2; 3

Соответственно количество элементов массива равняется N.

Алгоритм которым я перебираю комбинации взят у Паблито с этой темы.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class MainClass {
    
    public static void main(String[] args) {
                
        String[] arr = {"1", "2", "3", "4"};
            int count = fuctorial(arr.length);
            int max = arr.length - 1;
            System.out.println("Вариантов " + count);
            int shift = max;
            String t;
            while (count > 0) {
                t = arr[shift];
                arr[shift] = arr[shift - 1];
                arr[shift - 1] = t;
                print(arr);
                count--;
                if (shift < 2) {
                    shift = max;
                } else {
                    shift--;
                }
            }
    }
 
    static void print(String[] arr) {
        System.out.println(Arrays.toString(arr));
    }
 
    static int fuctorial(int n) {
        return (n > 0) ? n * fuctorial(n - 1) : 1;
    }
 
}

@Aviz__ · 20.07.2016, 15:05

Может это вам поможет Задача "Неудачные дни"

@vcrop · 20.07.2016, 18:35

Вот не знаю, насколько тебе подойдет? Здесь строки

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    public static Set<String> set = new HashSet();
    
    public static void Rearrange(String prefix, String str){
        set.add(prefix);
        for (char ch : str.toCharArray()) 
            Rearrange(prefix + ch, str.replaceFirst(ch + "", ""));
    }
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args){
        // TODO code application logic here
        Rearrange("", "123");
        for (String j : set) System.out.println(j);
        
    }

На выходе:
12
23
13
132
231
1
123
2
321
3
213
312
31
21
32

@RedPatrick · 20.07.2016, 18:41

Не по теме:

vcrop, find all permutations of a String? :) Для массива будет все же отличаться

@Zelmm · 21.07.2016, 09:32 **[ТС]**

RedPatrick, что самое интересное, я как раз со строками и работаю. В описании задачи числовой массив я взял как пример. А по факту то, чего я хочу добиться это всех возможных комбинаций отдельных слов в String, коих от 2 до 10, причем количество всегда четное.

@RedPatrick · 21.07.2016, 09:49

Zelmm, тогда vcrop уже дал то, что Вам нужно. Но вот вроде как классическое решение этой задачи:

Java
1
2
3
4
5
6
7
8
9
10
11
12
public static void permutation(String str) { 
    permutation("", str); 
}
 
private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

@Zelmm · 21.07.2016, 10:15 **[ТС]**

RedPatrick, да, Вы правы. Это действительно то, что нужно. А Ваш алгоритм, пока не понял почему, иногда дублирует результаты.

@RedPatrick · 21.07.2016, 10:21

Ну и на самом деле вот точно нужный код:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Main  {
    public static void main(String args[]) {
        String[] s = {"Was", "it", "a", "cat", "I", "saw"};
        permutate(s);
    }
 
    public static void permutate(String[] arr){
        permuteIteration(arr, 0);
    }
 
    private static void permuteIteration(String[] arr, int index){
        //последняя итерация
        if(index >= arr.length - 1){ 
            for(String s: arr) System.out.print(s + " ");
            System.out.println("");
            return;
        }
        
        for(int i = index; i < arr.length; i++){ 
            String temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
 
            permuteIteration(arr, index+1);
 
            temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
        }
    }
}

@Zelmm · 21.07.2016, 10:28 **[ТС]**

RedPatrick, а отдельные комбинации из набора но с меньшим количеством слов?

В любом случае спасибо за алгоритмы вам обоим. Сам бы я до этого додумывался очень долго.

@RedPatrick · 21.07.2016, 11:40

Zelmm, Ну давайте перегрузим функции, limit - количество необходимых слов

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void permutate(String[] arr, int limit){
        permuteIteration(arr, 0, 3);
    }
 
    private static void permuteIteration(String[] arr, int index, int limit){
        //последняя итерация
        if(index >= limit){ 
            for(int i = 0; i < limit; i++) System.out.print(arr[i] + " ");
            System.out.println("");
            return;
        }
        
        for(int i = index; i < arr.length; i++){ 
            String temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
 
            permuteIteration(arr, index+1, limit);
 
            temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
        }
    }

@Zelmm · 21.07.2016, 14:29 **[ТС]**

Невероятно, спасибо огромное.
Сам пока до таких конструкций не смогу додуматься.

Добавлено через 2 часа 17 минут
RedPatrick и vcrop, еще раз спасибо вам обоим большое. Так же спасибо Aviz__, за предложенную задачку (порешаю на досуге).
Собственно мне не столько нужно было вывести это действие на консоль, сколько все варианты использовать еще и в другом месте программы. И вот, с 11:40, как RedPatrick предложил свой последний алгоритм я мучился над тем, как мне вытащить все результаты в корректном для использования виде. В итоге вспомнил про StringBuilder и все получилось

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class MainClass {
    
static int count = 0;
static ArrayList<String> arrList = new ArrayList<>();
static StringBuilder sb = new StringBuilder();
    
    public static void main(String args[]) {
        
 
 
        String[] s = {"Was", "it", "a", "cat", "I", "saw"};
        for (int i = 1; i < s.length + 1; i ++)
            permutate(s, i);
        for (String string : arrList) System.out.println(++count + ": " + string);
    }       
    
    public static void permutate(String[] arr, int limit){
        permuteIteration(arr, 0, limit);
    }
 
    private static void permuteIteration(String[] arr, int index, int limit){
        //последняя итерация
        if(index >= limit){
            for(int i = 0; i < limit; i++) sb.append(arr[i] + " ");
            arrList.add(sb.toString());
            sb.delete(0, sb.length());
            return;
        }
 
        for(int i = index; i < arr.length; i++){ 
            String temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
 
            permuteIteration(arr, index+1, limit);
 
            temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
        }
    }
}

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

Комбинации всех возможных элементов массива

Решение

Решение

@Aviz__ 2736 / 2046 / 506 Регистрация: 17.02.2014 Сообщений: 9,462
	20.07.2016, 15:05
	Может это вам поможет Задача "Неудачные дни" 1

@RedPatrick
	20.07.2016, 18:41
	Не по теме: vcrop, find all permutations of a String? :) Для массива будет все же отличаться 0

@Zelmm 11 / 2 / 0 Регистрация: 20.07.2016 Сообщений: 35
	21.07.2016, 09:32 [ТС]
	RedPatrick, что самое интересное, я как раз со строками и работаю. В описании задачи числовой массив я взял как пример. А по факту то, чего я хочу добиться это всех возможных комбинаций отдельных слов в String, коих от 2 до 10, причем количество всегда четное. 0

@Zelmm 11 / 2 / 0 Регистрация: 20.07.2016 Сообщений: 35
	21.07.2016, 10:15 [ТС]
	RedPatrick, да, Вы правы. Это действительно то, что нужно. А Ваш алгоритм, пока не понял почему, иногда дублирует результаты. 0

@Zelmm 11 / 2 / 0 Регистрация: 20.07.2016 Сообщений: 35
	21.07.2016, 10:28 [ТС]
	RedPatrick, а отдельные комбинации из набора но с меньшим количеством слов? В любом случае спасибо за алгоритмы вам обоим. Сам бы я до этого додумывался очень долго. 0