Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Kombinationsfinder {
- static void print(String s) {
- System.out.println(s);
- }
- static List<Integer> listSort(List<Integer> summanden) {
- Collections.sort(summanden);
- Collections.reverse(summanden);
- return summanden;
- }
- static String addToOutputString(String s, int count, int token, String add) {
- if (count>1)
- s+=(""+count+" * "+token+""+add);
- else
- s+=(""+token+""+add);
- return s;
- }
- static String listToString(List<Integer> liste) {
- String s = "";
- for (Integer v : liste) {
- if (liste.indexOf(v)==liste.size()-1)
- s+=(String.valueOf(v)+"");
- else
- s+=(String.valueOf(v)+", ");
- }
- return s;
- }
- static String listToShortString(List<Integer> liste) {
- String s = "";
- int count = 0;
- int token = 0;
- int curtok = 0;
- for (int i=0; i<liste.size(); i++) {
- curtok = liste.get(i);
- if (token == 0)
- token = curtok;
- if (curtok == token) {
- count++;
- } else {
- s=addToOutputString(s,count,token," + ");
- count=1;
- token=curtok;
- }
- }
- s=addToOutputString(s,count,token,"");
- return s;
- }
- static int listSum(List<Integer> liste) {
- int summe = 0;
- for (Integer v : liste)
- summe+=v;
- return summe;
- }
- static List<Integer> standardValues() {
- List<Integer> l = new ArrayList<Integer>();
- l.add(3);
- l.add(2);
- return l;
- }
- static int findCurrentPointer(List<Integer> s, int v) {
- return (s.indexOf(v)+1);
- }
- public static void main(String args[]) {
- int summe = 0;
- List<Integer> summanden = new ArrayList<Integer>();
- int magicnumber = 99;
- try {
- if (args.length<3) {
- print("Zu wenig Parameter (mindestens 3)! Übernehme Standardauswahl:");
- summanden=standardValues();
- print("" + magicnumber + ", " + listToString(summanden));
- print("--------------------------------");
- } else if(args.length>101) {
- print("Zu viele Parameter! 100 Summanden maximal! Übernehme Standardauswahl:");
- summanden=standardValues();
- print("" + magicnumber + ", " + listToString(summanden));
- print("--------------------------------");
- } else {
- magicnumber = Integer.parseInt(args[0]);
- for (int i=1; i<args.length; i++) {
- summanden.add(Integer.parseInt(args[i]));
- }
- print("Finde alle Kombinationen der Werte: ");
- print("" + magicnumber + ", " + listToString(summanden));
- print("--------------------------------");
- }
- } catch (Exception e) {
- print("Parameter fehlerhaft! Nur ints sind erlaubt!");
- print("Die erste Zahl ist gesucht, die max 100 Zahlen dahinter stellen die erlaubten Glieder dar.");
- print("BeispieL: \"99 3 2\" als Parameter ermittelt alle Kombinationen von 99 mit den beiden Zahlen 2 und 3!");
- print("--------------------------------------------------------------");
- print("Übernehme Standardauswahl:");
- summanden=standardValues();
- print("" + magicnumber + ", " + listToString(summanden));
- }
- summanden = listSort(summanden);
- Boolean all_solutions = false;
- int loopcounter = 0;
- int loopmax = 1000000;
- int pointer = 0;
- int combicount = 0;
- int lowest = summanden.get(summanden.size()-1);
- List<Integer> liste = new ArrayList<Integer>();
- while (all_solutions==false && loopcounter<loopmax) {
- summe = listSum(liste);
- if (summe>=magicnumber) {
- if (summe == magicnumber) {
- print("" + listToShortString(liste) + " = " + magicnumber + " !!!");
- combicount++;
- }
- if (liste.get(0) == lowest) {
- print("--------------------------------\nAlle " + combicount + " Kombinationen in "+loopcounter+" Durchläufen gefunden!");
- all_solutions=true;
- break;
- }
- if (liste.get(liste.size()-1) > lowest) {
- liste.remove(liste.size()-1);
- pointer++;
- } else {
- for(int i=liste.size()-1; i>=0; i--) {
- if (liste.get(i) <= lowest)
- liste.remove(i);
- else
- break;
- }
- pointer = findCurrentPointer(summanden, liste.get(liste.size()-1));
- liste.remove(liste.get(liste.size()-1));
- }
- } else {
- liste.add(summanden.get(pointer));
- }
- loopcounter++;
- }
- if(loopcounter == loopmax)
- print("--------------------------------\n"+loopcounter+" Durchläufe berechnet. "+ combicount + " Kombinationen gefunden.");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement