Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Форум программистов и сисадминов Киберфорум > Форум программистов > Java > Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.91/11: Рейтинг темы: голосов - 11, средняя оценка - 4.91
1 / 1 / 1
Регистрация: 19.08.2015
Сообщений: 17
1

Комбинаторика с использованием PermutationIterator

23.07.2016, 10:05. Показов 2248. Ответов 5
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Нужно что бы получилось 12 комбинаций, в таком виде :
[0, 1, 2][3, 4]
[0, 1, 2][4, 3]
[0, 2, 1][3, 4]
[0, 2, 1][4, 3]
[2, 0, 1][3, 4]
[2, 0, 1][4, 3]
[2, 1, 0][3, 4]
[2, 1, 0][4, 3]
[1, 2, 0][3, 4]
[1, 2, 0][4, 3]
[1, 0, 2][3, 4]
[1, 0, 2][4, 3]

у меня получается:
[0, 1, 2][3, 4]
[0, 1, 2][4, 3]

я понимаю что с условиями я напутал, но не доходит какие условия в циклах я должен проставить.

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
43
44
45
46
47
48
49
50

public class Test {
 
                        public static void main(String[] args) {
    
 
                        List<Integer> ordersPrior1 = new ArrayList<Integer>();
                        List<Integer> ordersPrior2 = new ArrayList<Integer>();
            
                        for(int i=0; i<3; i++){  
                ordersPrior1.add(i);
            }
            
            for(int i=3; i<5; i++){  
                ordersPrior2.add(i);
            }
        
            PermutationIterator ordersfact1 = new PermutationIterator(ordersPrior1);
            PermutationIterator ordersfact2 = new PermutationIterator(ordersPrior2);
        
            int y,j=1;
            
            for (y=1; y < 7; y++){
            
                while(ordersfact1.hasNext()  && j<=y){
                    if(j==y){
                                    
                        List list1 = ordersfact1.next();
                    
                            while(ordersfact2.hasNext()){
                            
                                List list2 = ordersfact2.next();
                                                        
                                System.out.print(list1);        
                                System.out.println(list2);
                                                        
                            }
                                                        
                    }
                    else
                        ordersfact1.next();
                    j++;
                }
            
            }
            
            
            
            
    }
}
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 23.07.2016, 10:05
Ответы с готовыми решениями:

Комбинаторика
Даны числа от 1 до 40. Берем оттуда 6 любых цифр и получается комбинация из 6 цифр. Всего будет...

Комбинаторика
1.Составляются слова длины 4 из 32 букв русского алфавита так, что две соседние буквы этих слов...

Комбинаторика
Здравствуйте, уважаемые посетители. Прошу помощи в вопросе - есть задача: У нас есть коробка...

комбинаторика 1
В подьезде дома установлен замок с кодом. Дверь автоматически открывается,если в определенной...

5
6045 / 2160 / 753
Регистрация: 10.12.2010
Сообщений: 6,005
Записей в блоге: 3
19.09.2016, 10:52 2
Одна из самых клевых задач что я делал. Сделал слегка сложно для начинающего, но при желании разобраться реально. Работает с произвольно задаваемым числом массивов (и не обязательно массивов, что также клево). Алгоритм генерации перестановок взял с СО (вроде даже не сильно переделал) ибо самостоятельно сделать быструю реалиацию генератора перестановок сделать не сумел за те два дня что с задачей сидел. Короче вот классы:
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

public class Permutator<T> implements Iterator<T[]> {
 
    private T[] array;
 
    private int[] indices;
 
    private boolean hasNext;
 
    private T[] outputArray;
 
    public Permutator(T[] originalArray)
    {
        array = originalArray.clone();
 
        indices = new int[originalArray.length];
 
        Map<T, Integer> hashMap = new HashMap<T, Integer>();
        for (int i = 0; i < originalArray.length; i++)
        {
            Integer item = hashMap.get(originalArray[i]);
            if (item == null)
            {
                hashMap.put(originalArray[i], i);
                item = i;
            }
            indices[i] = item.intValue();
        }
        Arrays.sort(indices);
 
        outputArray = (T[]) Array.newInstance(originalArray.getClass().getComponentType(), originalArray.length);
 
        fillOutputArray();
 
        hasNext = true;
    }
 
    private void fillOutputArray()
    {
        for (int i = 0; i < indices.length; i++)
            outputArray[i] = array[indices[i]];
    }
 
    public T[] getOutputArray()
    {
        return outputArray;
    }
 
    @Override
    public boolean hasNext()
    {
        return hasNext;
    }
 
    @Override
    public T[] next() 
    {
        if (!hasNext)
            throw new NoSuchElementException();
 
        fillOutputArray();
 
        hasNext = getNextPermutation();
 
        return outputArray;
    }
 
    private boolean getNextPermutation()
    {
        boolean wasGenerated = false;
 
        int tail = indices.length - 1;
        while ((tail > 0) && !wasGenerated)
        {
            if (indices[tail - 1] < indices[tail])
            {
                int temp = indices.length - 1;
 
                while (indices[tail - 1] >= indices[temp]) temp--;
 
                swap(indices, tail - 1, temp);
 
                int i = tail;
                int j = indices.length - 1;
                while (i < j)
                {
                    swap(indices, i, j);
                    i++;
                    j--;
                }
                wasGenerated = true;
            }
            tail--;
        }
 
        return wasGenerated;
    }
 
    private void swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 
    @Override
    public void remove() {
 
    }
 
    public void reinit()
    {
        Arrays.sort(indices);
        hasNext = true;
    }
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

public class CombinedPermutator<T> implements Iterator<ArrayList<T[]>> {
 
    private ArrayList<Permutator<T>> permutatorsList;
 
    private boolean hasNext;
 
    private ArrayList<T[]> outputArrayList;
 
    public CombinedPermutator(ArrayList<T[]> arrayList)
    {
        permutatorsList = new ArrayList<Permutator<T>>();
 
        for (T[] array : arrayList)
            permutatorsList.add(new Permutator<T>(array.clone()));
 
        outputArrayList = new ArrayList<T[]>();
 
        for (int i = 0; i < permutatorsList.size() - 1; i++)
        {
            if (permutatorsList.get(i).hasNext())
                permutatorsList.get(i).next();
        }
 
        hasNext = true;
 
    }
 
    @Override
    public boolean hasNext()
    {
        return hasNext;
    }
 
    @Override
    public ArrayList<T[]> next()
    {
        if (!hasNext)
            throw new NoSuchElementException();
 
        if (!outputArrayList.isEmpty())
            outputArrayList.clear();
 
        for (Permutator<T> aPermutatorsList : permutatorsList)
            outputArrayList.add(aPermutatorsList.getOutputArray());
 
        hasNext = permutate();
 
        return outputArrayList;
    }
 
    private boolean permutate()
    {
        boolean flag = false;
 
        int i = permutatorsList.size() - 1;
 
        while ((i > -1) && !flag)
        {
            if (i == 0)
            {
                if (permutatorsList.get(i).hasNext())
                    permutatorsList.get(i).next();
            }
            else
            {
                if (!permutatorsList.get(i).hasNext())
                    permutatorsList.get(i).reinit();
                else
                    flag = true;
 
                permutatorsList.get(i).next();
            }
 
            i--;
        }
 
        return canPermutate();
    }
 
    private boolean canPermutate()
    {
        boolean canPermutate = false;
 
        int i = 0;
 
        while ((i < permutatorsList.size()) && !canPermutate)
        {
            canPermutate = permutatorsList.get(i).hasNext();
            i++;
        }
 
        return canPermutate;
    }
 
    @Override
    public void remove()
    {
 
    }
}
Тест с вашими данными:
Java
1
2
3
4
5
6
7
8
9
10
11
12

public class Main {
    public static void main(String[] args)
    {
        CombinedPermutator<Integer> cm = new CombinedPermutator<Integer>(new ArrayList<Integer[]>(Arrays.asList(
                new Integer[]{0, 1, 2},
                new Integer[]{3, 4})));
 
        while (cm.hasNext())
            System.out.println(Arrays.deepToString(cm.next().toArray()));
 
    }
}
Результат:
Кликните здесь для просмотра всего текста
Код
[[0, 1, 2], [3, 4]]
[[0, 1, 2], [4, 3]]
[[0, 2, 1], [3, 4]]
[[0, 2, 1], [4, 3]]
[[1, 0, 2], [3, 4]]
[[1, 0, 2], [4, 3]]
[[1, 2, 0], [3, 4]]
[[1, 2, 0], [4, 3]]
[[2, 0, 1], [3, 4]]
[[2, 0, 1], [4, 3]]
[[2, 1, 0], [3, 4]]
[[2, 1, 0], [4, 3]]
Тест посложнее:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Main {
    public static void main(String[] args)
    {
        CombinedPermutator<Integer> cm = new CombinedPermutator<Integer>(new ArrayList<Integer[]>(Arrays.asList(
                new Integer[]{0, 1, 2},
                new Integer[]{3, 4},
                new Integer[]{5, 6, 7}
        )));
 
        while (cm.hasNext())
            System.out.println(Arrays.deepToString(cm.next().toArray()));
 
    }
}
Результат:
Кликните здесь для просмотра всего текста
Код
[[0, 1, 2], [3, 4], [5, 6, 7]]
[[0, 1, 2], [3, 4], [5, 7, 6]]
[[0, 1, 2], [3, 4], [6, 5, 7]]
[[0, 1, 2], [3, 4], [6, 7, 5]]
[[0, 1, 2], [3, 4], [7, 5, 6]]
[[0, 1, 2], [3, 4], [7, 6, 5]]
[[0, 1, 2], [4, 3], [5, 6, 7]]
[[0, 1, 2], [4, 3], [5, 7, 6]]
[[0, 1, 2], [4, 3], [6, 5, 7]]
[[0, 1, 2], [4, 3], [6, 7, 5]]
[[0, 1, 2], [4, 3], [7, 5, 6]]
[[0, 1, 2], [4, 3], [7, 6, 5]]
[[0, 2, 1], [3, 4], [5, 6, 7]]
[[0, 2, 1], [3, 4], [5, 7, 6]]
[[0, 2, 1], [3, 4], [6, 5, 7]]
[[0, 2, 1], [3, 4], [6, 7, 5]]
[[0, 2, 1], [3, 4], [7, 5, 6]]
[[0, 2, 1], [3, 4], [7, 6, 5]]
[[0, 2, 1], [4, 3], [5, 6, 7]]
[[0, 2, 1], [4, 3], [5, 7, 6]]
[[0, 2, 1], [4, 3], [6, 5, 7]]
[[0, 2, 1], [4, 3], [6, 7, 5]]
[[0, 2, 1], [4, 3], [7, 5, 6]]
[[0, 2, 1], [4, 3], [7, 6, 5]]
[[1, 0, 2], [3, 4], [5, 6, 7]]
[[1, 0, 2], [3, 4], [5, 7, 6]]
[[1, 0, 2], [3, 4], [6, 5, 7]]
[[1, 0, 2], [3, 4], [6, 7, 5]]
[[1, 0, 2], [3, 4], [7, 5, 6]]
[[1, 0, 2], [3, 4], [7, 6, 5]]
[[1, 0, 2], [4, 3], [5, 6, 7]]
[[1, 0, 2], [4, 3], [5, 7, 6]]
[[1, 0, 2], [4, 3], [6, 5, 7]]
[[1, 0, 2], [4, 3], [6, 7, 5]]
[[1, 0, 2], [4, 3], [7, 5, 6]]
[[1, 0, 2], [4, 3], [7, 6, 5]]
[[1, 2, 0], [3, 4], [5, 6, 7]]
[[1, 2, 0], [3, 4], [5, 7, 6]]
[[1, 2, 0], [3, 4], [6, 5, 7]]
[[1, 2, 0], [3, 4], [6, 7, 5]]
[[1, 2, 0], [3, 4], [7, 5, 6]]
[[1, 2, 0], [3, 4], [7, 6, 5]]
[[1, 2, 0], [4, 3], [5, 6, 7]]
[[1, 2, 0], [4, 3], [5, 7, 6]]
[[1, 2, 0], [4, 3], [6, 5, 7]]
[[1, 2, 0], [4, 3], [6, 7, 5]]
[[1, 2, 0], [4, 3], [7, 5, 6]]
[[1, 2, 0], [4, 3], [7, 6, 5]]
[[2, 0, 1], [3, 4], [5, 6, 7]]
[[2, 0, 1], [3, 4], [5, 7, 6]]
[[2, 0, 1], [3, 4], [6, 5, 7]]
[[2, 0, 1], [3, 4], [6, 7, 5]]
[[2, 0, 1], [3, 4], [7, 5, 6]]
[[2, 0, 1], [3, 4], [7, 6, 5]]
[[2, 0, 1], [4, 3], [5, 6, 7]]
[[2, 0, 1], [4, 3], [5, 7, 6]]
[[2, 0, 1], [4, 3], [6, 5, 7]]
[[2, 0, 1], [4, 3], [6, 7, 5]]
[[2, 0, 1], [4, 3], [7, 5, 6]]
[[2, 0, 1], [4, 3], [7, 6, 5]]
[[2, 1, 0], [3, 4], [5, 6, 7]]
[[2, 1, 0], [3, 4], [5, 7, 6]]
[[2, 1, 0], [3, 4], [6, 5, 7]]
[[2, 1, 0], [3, 4], [6, 7, 5]]
[[2, 1, 0], [3, 4], [7, 5, 6]]
[[2, 1, 0], [3, 4], [7, 6, 5]]
[[2, 1, 0], [4, 3], [5, 6, 7]]
[[2, 1, 0], [4, 3], [5, 7, 6]]
[[2, 1, 0], [4, 3], [6, 5, 7]]
[[2, 1, 0], [4, 3], [6, 7, 5]]
[[2, 1, 0], [4, 3], [7, 5, 6]]
[[2, 1, 0], [4, 3], [7, 6, 5]]
4
31 / 31 / 12
Регистрация: 25.07.2015
Сообщений: 120
19.09.2016, 18:55 3
1982Darkness, HighPredator, можно условие или ссылку на задачу. Интересно будет в свободное время заняться этим
0
6045 / 2160 / 753
Регистрация: 10.12.2010
Сообщений: 6,005
Записей в блоге: 3
20.09.2016, 09:05 4
striker24, формального условия я не видел, поэтому сделал по примеру и обобщил для произвольного числа массивов.
0
5 / 3 / 1
Регистрация: 12.05.2019
Сообщений: 201
05.11.2022, 23:53 5
Это шикарно)) Правда) Ушло в закладочки))
0
5 / 3 / 1
Регистрация: 12.05.2019
Сообщений: 201
06.11.2022, 13:17 6
спустя сутки теста - все не так радужно))

что мне нужно - найти все возможные комбинации из известных 12ти слов.
подключаю ту красоту что выше - все работает нормально первые тысяч 5 вариантов. Потом слова в конце итоговой комбинации начинают повторяться.
0
06.11.2022, 13:17
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 06.11.2022, 13:17
Помогаю со студенческими работами здесь

комбинаторика)
помогите разобраться с задачами: 1) в коробке 8 одинак. изделий, причем половина из них окрашены....

Комбинаторика
Сколько шестизначных чисел можно составить из 1, 2, 3, 4, 5, 6, если в каждом числе четных цифр...

комбинаторика
Объявлен конкурс на получение грантов. В конкурсе принимают участие n человек. Гранты выдаются...

Комбинаторика
Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его...

Комбинаторика
Есть два задание, но немогу понять как это всьо решается! Если кто может, помогите решить!...

Комбинаторика на С++
Нужно составить программу, или скорее функцию, которая для заданного натурального числа k выводит...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru