Хочу начать с того, что являюсь новичком, мой код далёк от идеальности и скорей всего его нужно править или переделывать.
Так вот, задача стоит вот в чём: Программа должна выводить все перестановки мультимножества без повторений, мультимножество вводиться с клавиатуры.
Сам код приведён ниже. Сразу скажу, что он работает, при этом весьма корректно.
Суть проблемы такова: программа работает только до ввода 10 чисел, дальше не хочет. Так как 10! - это уже 4млн комбинаций. Аррайлист заполнен видимо до упора, в результате выникает Exeption OutOfMemoryError. Что делать ? Как быть? Буду рад любой помощи.
Забыл сказать об самой теории. Мультимножество - набор чисел.
A = {1^2 ,2^3 ,3^3 ,4^2 ,5^1};
Тут степень - количество повторов. Т.е. это мультмн. можна было предствить в виде:
A = {1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5};
На основании таких чисел нужно строить перестановки без повторений.
Моя прога:
1.Я достаю такое множество в Аррайлист
2.Рекурсивно делаю перестановки
3.Отсееваю лишние с помощью Хэшсэта
4.Записываю в файл. Т.к. в консоле все перестановки не вмещаются.
import java.io.*;
import java.util.*;
import static java.util.Collections.swap;
public class Main {
private static ArrayList <String> rec_filter = new ArrayList<>();
private static String fileName = "new_file.txt";
private static ArrayList<String> in = new ArrayList<String>();
public static ArrayList<Integer> return_Arrlist() throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> list = new ArrayList<Integer>();
while (true) {
String s = bufferedReader.readLine();
if (s.equals("")) break;
int num = Integer.parseInt(s);
System.out.print(num + "^");
String tmp_step = bufferedReader.readLine();
int stepin = Integer.parseInt(tmp_step);
in.add(num + "^" + tmp_step);
while (stepin > 0) {
list.add(num);
stepin--;
}
}
System.out.println("Введена мультимножина: " +"\n А = " +in);
return list;
}
public static void permute(ArrayList<Integer> list, int start) throws IOException {
for (int j = start; j <= list.size() - 1; j++) {
swap(list, start, j);
//System.out.println(list);
permute(list, start + 1);
swap(list, start, j);
}
rec_filter.add(list.toString());
}
public static void main(String[] args) throws IOException {
permute(return_Arrlist(), 0);
int count = 0;
List <String> list = rec_filter;
Set <String> set = new HashSet<>(list);
rec_filter.removeAll(rec_filter);
list.removeAll(list);
in.removeAll(in);
long startTime = System.currentTimeMillis();
File file = new File(fileName);
try {
BufferedWriter writer = new BufferedWriter(new FileWriter(file, true));
for (Iterator iter = set.iterator(); iter.hasNext();) {
count++;
//System.out.println(count+") "+ iter.next());
writer.write(count+") "+ iter.next()+"\n");
}
writer.close();
}
catch (Exception ex){
ex.printStackTrace();
}
String s = "----------------------------------------\n";
System.out.printf("%s",s);
System.out.println("Всього можливих комбінацій: " +count);
System.out.printf("%s",s);
long timeSpent = System.currentTimeMillis() - startTime;
System.out.println("програма виконувадась " + (timeSpent*10e-6) + " секунд");
}
}
Простой
