Suche Permutationsalgo

[chris_L_1980]

Hallo,
ich suche einen bestimmten Permutationsalgorithmus, leider ist mein Einfallsreichtum wie man den implementieren kann im moment bei 0

Also ich habe eine Zeile der länge n und eine beliebige anzahl an blöcken, die in diese Zeile reinpassen mit mindestens einer Zelle abstand.
Z.B. hat die Zeile eine länge von 5, und ich hab 2 Blöcke mit der länge "1" und "2". dann gäbe es als möglichkeiten(1 für Block, 0 für frei):
10110
10011
01011

Hierfür such ich einen Algorithmus, der als Parameter die Zeilenlänge und ein int-Array mit den Blocklängen bekommt.

 

[nrg]

also vllt liegt es an meinem Zustand, aber ich kann grad noch nicht wirklich nachvollziehen, was du willst

 

[Landei]

Für alle möglichen Positionen des ersten Blocks: Block und "umgebende" Leerzeichen positionieren, mit den restlichen Blöcken und dem entsprechend verkürzten Array das ganze wiederholen...

 

[Marco13]

Man könnte sich da verschiedene Ansätze überlegen... Wenn es nicht DER optimale sein muss, könnte man relativ "einfache" Workarounds suchen, wie z.B. alle Reihenfolgen für die Blöcke bestimmen, und dann überprüfen, ob das nach dem Einfügen der benötigten Leerzeichen noch passt. Dass die Leerzeichen am Anfang und am Ende "optional" sind, und dass ein Leerzeichen rechts von A und ein Leerzeichen links von B nicht ZWEI Leerzeichen sind, sondern EINS (eben zwischen A und B) macht das Problem ansonsten vermutlich ziemlich fummelig...

 

[Landei]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BlockAlgo {

    public static List<List<Integer>> solutions(int length, int... blocks) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (blocks.length == 0) {
            result.add(Collections.nCopies(length, 0));
        } else {
            boolean last = blocks.length == 1;
            int minLength = -1;
            for(int b : blocks) {
                minLength += b + 1;
            }
            for(int start = 0; start <= length - minLength; start++) {
                List<Integer> initial = new ArrayList<Integer>();
                initial.addAll(Collections.nCopies(start, 0));
                initial.addAll(Collections.nCopies(blocks[0], 1));
                if(! last) {
                    initial.add(0);
                }
                for(List subList : solutions(length - start - blocks[0] -
                        (last ? 0 : 1),
                        Arrays.copyOfRange(blocks, 1, blocks.length))) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.addAll(initial);
                    list.addAll(subList);
                    result.add(list);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        for(List<Integer> list : solutions(23, 1, 3, 2, 5, 4)) {
           System.out.println(list);
        }
    }
}

 

[chris_L_1980]

Hallo,
verzeiht das ich mich so spät melde, aber gestern war wieder so ein Tag, an dem man froh ist, wenn man endlich nach Hause kommt...

also erstmal vielen Dank für den algo. funktioniert wunderbar und macht genau das, was er machen soll
hab allerdings noch ein paar kleine verständnisfragen.
1. Steht minLength für die am weitesten rechts liegende Anfangsposition des ersten blocks?
2. und warum ist der wert -1 am anfang?

ansonsten hab ich denke ich alles ziemlich genau verstanden und bedanke mich nochmal

 

[Landei]

Hallo,
verzeiht das ich mich so spät melde, aber gestern war wieder so ein Tag, an dem man froh ist, wenn man endlich nach Hause kommt...

also erstmal vielen Dank für den algo. funktioniert wunderbar und macht genau das, was er machen soll
hab allerdings noch ein paar kleine verständnisfragen.
1. Steht minLength für die am weitesten rechts liegende Anfangsposition des ersten blocks?

minLength ist die minimale Länge, bei der ich alle Blöcke noch unterbringen kann.

2. und warum ist der wert -1 am anfang?

Weil der "rechteste" Block rechts neben sich keine Leerstelle braucht.