CODEWITHSUNDEEP
javadynamic-programming
Vincent
Vincent

Reputation: 11

Optimizing item order in an ArrayList

I have an ArrayList of colors and their frequency of appearance. My program should calculate a reordering of those items that maximizes the minimum distance between two equal bricks.

For example, given input consisting of 4*brick 1 (x), 3*brick 2 (y), and 5*brick 3 (z), one correct output would be: z y x z x z y x z x y.

My code does not produce good solutions. In particular, sometimes there are 2 equal bricks at the end, which is the worst case.

import java.util.ArrayList;
import java.util.Collections;

public class Calc {
    // private ArrayList<Wimpel> w = new ArrayList<Brick>();
    private String bKette = "";

    public String bestOrder(ArrayList<Brick> w) {
        while (!w.isEmpty()) {

            if (w.get(0).getFrequency() > 0) {
                bChain += w.get(0).getColor() + "|";
                Brick brick = new Wimpel(w.get(0).getVariant(), w.get(0).getFrequency() - 1);
                w.remove(0);
                w.add(brick);
                // bestOrder(w);
            } else {
                w.remove(0);
            }
            bestOrder(w);
        }
        return bOrder;
    }

    public int Solutions(ArrayList<Wimpel> w) {
        ArrayList<Brick> tmp = new ArrayList<Brick>(w);
        int l = 1;

        int counter = (int) w.stream().filter(c -> Collections.max(tmp).getFrequency() == c.getFrequency()).count();
        l = (int) (fakultaet(counter) * fakultaet((tmp.size() - counter)));
        return l;
    }

    public static long fakultaet(int n) {
        return n == 0 ? 1 : n * fakultaet(n - 1);
    }
}

How can make my code choose an optimal order?

Upvotes: 1

Views: 91

Answers (1)

John Bollinger
John Bollinger

Reputation: 181159

We will not perform your exercise for you, but we will give you some advice.

Consider your current approach: it operates by filling the result string by cycling through the bricks, choosing one item from each brick in turn as long as any items remain in that brick. But this approach is certain to fail when one brick contains at least two items more than any other, because then only that brick remains at the end, and all its remaining items have to be inserted one after the other.

That is, the problem is not that your code is buggy per se, but rather that your whole strategy is incorrect for the problem. You need something different.

Now, consider the problem itself. Which items will appear at the shortest distance apart in a correct ordering? Those having the highest frequency, of course. And you can compute that minimum distance based on the frequency and total number of items.
Suppose you arrange these most-constrained items first, at the known best distance.

What's left to do at this point? Well, you potentially have some more bricks with lesser frequency, and some more slots in which to accommodate their items. If you ignore the occupied slots altogether, you can treat this as a smaller version of the same problem you had before.

Upvotes: 1

Related Questions