この問題を処理するために必要な基本的なオブジェクトの1つは、要素の複数のインスタンスを含むことができる値の順序付けられていない集合であるBagまたはMultiSetです。残念ながら、Java Collectionsフレームワークはこれをサポートしていません。 Listを動作させようとするのではなく、われわれが必要とする機能だけで、非常に基本的なバージョンを書くことができます。 （GuavaライブラリはMultiSetを持っているので、プロダクションコードのためにそれを見ることができます）。
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.TreeMap;
public class Bag<E>
{
private Map<E, Integer> m_values;
public Bag()
{
m_values = new TreeMap<E, Integer>();
}
public Bag(Iterable<E> arr)
{
this();
for(E v : arr)
{
add(v);
}
}
public Bag(Bag<E> b)
{
this();
for(E v : b.values())
{
set(v, b.count(v));
}
}
public void add(E v)
{
Integer count = m_values.get(v);
m_values.put(v, count == null ? 1 : count+1);
}
public void add(Bag<E> b)
{
for(E v : b.values())
{
Integer count = m_values.get(v);
m_values.put(v, count == null ? b.count(v) : count+b.count(v));
}
}
public void remove(E v)
{
Integer count = m_values.get(v);
if(count == null) throw new NoSuchElementException();
if(count == 1)
m_values.remove(v);
else
m_values.put(v, count-1);
}
public void remove(Bag<E> b)
{
for(E v : b.values())
{
Integer count = m_values.get(v);
Integer bcount = b.count(v);
if(count == null || count < bcount) throw new NoSuchElementException();
if(count == bcount)
m_values.remove(v);
else
m_values.put(v, count-bcount);
}
}
public boolean contains(Bag<E> b)
{
for(E v : b.values())
{
if(count(v) < b.count(v)) return false;
}
return true;
}
public void set(E v, int count)
{
if(count == 0)
m_values.remove(v);
else
m_values.put(v, count);
}
public int count(E v)
{
Integer count = m_values.get(v);
return count == null ? 0 : count;
}
public Iterable<E> values()
{
return m_values.keySet();
}
public String toString()
{
StringBuilder b = new StringBuilder();
b.append("[");
for(E v : values())
{
for(int i=0; i<count(v); i++)
{
b.append(v + " ");
}
}
b.deleteCharAt(b.length()-1);
b.append("]");
return b.toString();
}
}
問題を解決するための最初のステップは、候補者のリストを生成することである。我々は、入力配列からのサブセットを生成することによって、これを行うことが5にその合計を設定しますが、我々は重複を含まないように注意する必要があります。このためのコードそれほど悪くはありませんが、少し効率的な場合、それはちょうどあなたが興味を持っている数の可能なすべてのパーティションを生成するために、実際にははるかに簡単ですが、この場合は5
import java.util.ArrayList;
import java.util.List;
public class Partition
{
public static List<Bag<Integer>> partitions(int n)
{
return new Partition(n).partitions;
}
private List<Bag<Integer>> partitions;
private Bag<Integer> current;
private Partition(int n)
{
partitions = new ArrayList<>();
current = new Bag<Integer>();
build(n, n);
}
private void build(int n, int max)
{
if (n == 0)
{
partitions.add(0, new Bag<Integer>(current));
}
for (int i = Math.min(max, n); i >= 1; i--)
{
current.add(i);
build(n - i, i);
current.remove(i);
}
}
public static void main(String[] args)
{
for (Bag<Integer> b : partitions(5))
{
System.out.println(b);
}
}
}
出力：
[1 1 1 1 1]
[1 1 1 2]
[1 2 2]
[1 1 3]
[2 3]
[1 4]
[5]
ここで、入力からこれらのパーティションの最大セットを抽出する再帰ルーチンを書くことができます。厄介な部分は、既に見たソリューションのサブセットではないセットを見つけたときに、無視することができるようにすることです。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Dice
{
public static List<List<Bag<Integer>>> picks(Integer[] diceArr, int k)
{
return new Dice(diceArr, k).output;
}
private List<List<Bag<Integer>>> output;
private List<Bag<Integer>> current;
private List<Bag<Integer>> partitions;
private Bag<Integer> dice;
private Dice(Integer[] diceArr, int k)
{
output = new ArrayList<>();
current = new ArrayList<>();
partitions = Partition.partitions(5);
dice = new Bag<>(Arrays.asList(diceArr));
build(0);
}
private void build(int pos)
{
for (int i=pos; i<partitions.size(); i++)
{
Bag<Integer> partition = partitions.get(i);
if(dice.contains(partition))
{
dice.remove(partition);
current.add(partition);
build(i);
current.remove(partition);
dice.add(partition);
}
}
// Only add the current list of partitions if we haven't already seen it
if(!current.isEmpty())
{
boolean seen = false;
for(List<Bag<Integer>> prev : output)
{
if(prev.containsAll(current))
{
seen = true;
break;
}
}
if (!seen) output.add(new ArrayList<>(current));
}
}
public static void main(String[] args)
{
int count = 5;
Integer[] dice = {1, 1, 1, 2, 4, 4};
List<List<Bag<Integer>>> picks = picks(dice, count);
for(List<Bag<Integer>> pick : picks)
{
System.out.println(pick);
}
}
}
{1、1、1、2、4、4}の出力：
[[1 1 1 2]]
[[1 4], [1 4]]
出力の{1、1、1、2、3、4、4、4、5 }：
[[1 1 1 2], [5]]
[[1 1 3], [1 4], [5]]
[[2 3], [1 4], [1 4], [1 4], [5]]
期待出力リストに「1 4」が2回しか表示されないのはなぜですか？ – templatetypedef
あなたが今得する出力は実際にはあなたが望むものよりも正確です。 6つの可能な組み合わせがあります。 – baao
あなたは出力に3行を意味するのではなく、7行を意味します。プログラムは正しいです。 –