次のようなテキストファイルがあります。
A
B
C
そして、各要素には次のようなサブセットがあります。
A = { a1, a2, a3 }
B = { b1, b2 }
C = { c1, c2, c3 }
私はこれを生成したい:
a1、b1、c1
a2、b1、c1
a3、b1、c1
a1、b2、c1
a1、b1、c2
a1、b1、c3
テキスト ファイル内の要素の数がわかりません (たとえば、A、B、C、D、E など)。サブセットのサイズはさまざまです。
おそらく「配列内の位置」と「配列のインデックス」の2つのインデックスを持つ再帰関数だと思いますが、これらすべてを実装する方法が本当にわかりません。
同じ入力でデカルト積を行う関数を適応させようとさえしましたが、完全に失敗しました。デカルト積を生成する必要はありません。
すべてのリストの最初の要素で構成される「基本リスト」を作成します。次に、すべてのリストのすべての要素をループします。そのような要素ごとに、その要素で適切な位置にある基本リストを更新し、この更新されたリストをリストの集計に追加します。
以下に実装例を含めました。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class AdjacentListGenerator {
public static <T> List<List<T>> generateAdjacentLists(List<List<T>> lists) {
List<List<T>> result = new ArrayList<List<T>>();
List<T> baseList = new ArrayList<T>();
// Generate the base list, which is comprised of all the first elements
for (List<T> list : lists) {
baseList.add(list.get(0));
}
result.add(baseList);
// Loop over each list, and for each element beyond the first, make a
// copy of the base list, update that element in place, and add it to
// our result
for (int list_i = 0; list_i < lists.size(); list_i++) {
List<T> list = lists.get(list_i);
for (int listElement_i = 1; listElement_i < list.size(); listElement_i++) {
List<T> updatedList = new ArrayList<T>(baseList);
updatedList.set(list_i, list.get(listElement_i));
result.add(updatedList);
}
}
return result;
}
public static void main(String... args) {
List<String> a = Arrays.asList(new String[] { "a1", "a2", "a3" });
List<String> b = Arrays.asList(new String[] { "b1", "b2" });
List<String> c = Arrays.asList(new String[] { "c1", "c2", "c3" });
List<List<String>> lists = new ArrayList<List<String>>();
lists.add(a);
lists.add(b);
lists.add(c);
for (List<String> list : AdjacentListGenerator
.generateAdjacentLists(lists)) {
System.out.println(list);
}
}
}
出力
[a1, b1, c1]
[a2, b1, c1]
[a3, b1, c1]
[a1, b2, c1]
[a1, b1, c2]
[a1, b1, c3]
List<List<Integer>> myInput = ...
for(int i=0; i<myInput.size(); i++){
for (int j=0; j<myInput.get(i).size(); j++){
if (j == 0 && i > 0){
continue;
}
List<Integer> result = new ArrayList<Integer>(myInput.size());
for(int k=0; k<myInput.size(); k++){
if (k == i){
result.add(myInput.get(k).get(j));
}else{
result.add(myInput.get(k).get(0));
}
}
System.out.println(result);
}
}
インデックスが反復されるリストであるすべてのリストをループします。
反復される内側のリストのサイズを見つけて、その回数ループします。
リストがインデックス付けされているリストでない限り、常に最初の要素を取得するリストをループします。その場合、反復リストから次の値を取得します。
みんなコンテナを使っているので、配列だけで解決しようと思います。
このアルゴリズムでは、最初の行を印刷するだけで、サブセットの次の要素を残りのサブセットの最初の要素で囲むことに焦点を当てています
String[] lines = { "a1, a2, a3", "b1, b2", "c1, c2, c3" };
String[][] array = new String[lines.length][];
for (int i = 0; i < lines.length; i++)
array[i] = lines[i].replaceAll(" +", "").split(",");
//lets type 1st row to ignore it in rest algoritm
System.out.print(array[0][0]);
for (int i = 1; i < array.length; i++)
System.out.print(", " + array[i][0]);
System.out.println();
//in rest of algorithm we must surround each element by
//1st element or rest rows, so lets iterate over each row
for (int row = 0; row < array.length; row++)
//and surround its elements
for (int col = 1; col < array[row].length; col++) {
//left surround
int i=0;
for (; i<row; i++)
System.out.print(array[i][0]+", ");
//
System.out.print(array[row][col]);
//right surround
for (i=i+1; i<array.length; i++)
System.out.print(", "+array[i][0]);
System.out.println();
}
問題の形式化：
これは多段階グラフにマッピングできます。多段階グラフのオンライン図をグーグルで検索するだけです。 あなたがやろうとしているのは、スーパーソース「S」からスーパーシンク「T」までのすべてのパスを印刷することです。あなたは同じことを読みたいかもしれません。さらに興味がある場合は、これはネットワークフローの問題にも関連しています。
私の答えは、データセットを既に並べ替えており、それらが正しい順序になっていることを前提としています。
public class SubsetPrinter
{
private static final String DELIMITER = ", ";
private static final String NEWLINE = System.getProperty("line.separator");
public static String printSubsets(Map<String, List<String>> elements)
{
List<String> lines = new ArrayList<String>();
for (Map.Entry<String, List<String>> entry : elements.entrySet())
{
for (String sub : entry.getValue())
{
String line = getLine(elements, entry.getKey(), sub);
if (!lines.contains(line))
{
lines.add(line);
}
}
}
return asString(lines);
}
private static String getLine(Map<String, List<String>> elements, String element, String sub)
{
StringBuilder line = null;
for (Map.Entry<String, List<String>> entry : elements.entrySet())
{
if (line == null)
{
line = new StringBuilder();
}
else
{
line.append(DELIMITER);
}
if (entry.getKey().equals(element))
{
line.append(sub);
}
else
{
line.append(entry.getValue().get(0)); // appends the first
}
}
return line.toString();
}
private static String asString(List<String> lines)
{
StringBuilder sb = null;
for (String line : lines)
{
if (sb == null)
{
sb = new StringBuilder();
}
else
{
sb.append(NEWLINE);
}
sb.append(line);
}
return sb.toString();
}
}
そして、テストは次のとおりです。
private Map<String, List<String>> getDataSet1()
{
Map<String, List<String>> map = new HashMap<String, List<String>>();
List<String> subsetA = Arrays.asList( new String[] { "a1", "a2", "a3" } );
List<String> subsetB = Arrays.asList( new String[] { "b1", "b2" } );
List<String> subsetC = Arrays.asList( new String[] { "c1", "c2", "c3" } );
map.put("A", subsetA);
map.put("B", subsetB);
map.put("C", subsetC);
return map;
}
@Test
public void testPrintSubsets()
{
Map<String, List<String>> elements = getDataSet1();
String output = SubsetPrinter.printSubsets(elements);
System.out.println(output);
}
出力：
a1, b1, c1
a2, b1, c1
a3, b1, c1
a1, b2, c1
a1, b1, c2
a1, b1, c3