組み合わせをチェックするプログラム

Question

全列挙した組み合わせから特定の組み合わせを除去して、残りの組み合わせを全列挙する方法があれば教えていただきたいです。

Comments

[yureighost]

支配関係が例で挙げられているようなわかりやすいパターンなら問題ないのですが、
実際には列挙されているパターンは会社と優先度が重ならないようになっているように見受けられます。

例えば、
3レコード目、A社1位、B社2位、C社2位。
6レコード目、A社2位、B社1位、C社2位。
7レコード目、A社2位、B社2位、C社1位。
はいずれもA、B、C社が3つ列挙されているパターンですが、
3レコード目のA社1位に対して、6、7レコード目はA社は2位ですが、
代わりにB、C社が1位になっていて優先度が高くなっています。

この3レコードは支配関係にあると言えるのでしょうか。

[reina1125]

yureighostさん
ご質問ありがとうございます。
A社、B社、C社間の優先順位を考慮していないので、その場合は支配関係にないと判断してそれぞれ出力する形となります。
また、下記のような場合も｢A社1位｣と｢A社の2位＋3位｣の優先順位が分からないので、この場合も支配関係にないと判断します。
A社1位、B社2位、C社2位
A社2位、A社3位、B社2位、C社2位

私の例の作り方が分かりにくくて申し訳ありません。表の数値を変えても正しく動くようにしたいと考えています。
よろしくお願いいたします。

[thkim0111]

コードを見て疑問に思ったのですが、プロジェクトが2つの組み合わせは考慮しなくていいのですか？
表の数値を変えたときに
{1,1,0,0}{0,0,1,1}
のようなパターンがあればプロジェクト2つの組み合わせも成り立つような気もするのですが。。

[reina1125]

thkim0111さん
数字を変えたパターンで考えていなかったので、見落としていました。
今、プロジェクト2つの場合も追加しました。
ご指摘ありがとうございます。

[reina1125]

例題を変更しました。

3レコード目、A社1位、B社2位、C社2位
5レコード目、A社２位、B社3位、C社2位

において、3レコード目は１レコード目に支配されているということになります。

3レコード目、A社1位、B社2位、C社2位
9レコード目、A社3位、B社2位、C社2位、C社3位

においては、A社とB社は１レコード目に支配されていますが、 「C社の2位」と「C社の2位+3位」の優先順位が不明なので支配関係にないと判断して出力します。

[yureighost]

この前提だと現在の列挙を書き出すプログラムが
プロジェクト二つで成り立つパターンが考慮されていないので割り出せませんね。
まずそこから直す必要があるようです。
それと私も前の例題で挙がられてるパターンのみだと思っていました。
情報を小出しにされると前に回答された方の作業が全て無駄になってしまうので、
考え得る限りの情報を出すようにお願いします。

[reina1125]

yureighostさん
プロジェクト二つで成り立つパターンを考慮するプログラムを追加しました。
申し訳ありませんでした。

[xebme]

static int ProjectB[][] = { { 1, 0, 1, 0 }, { 0, 0, 1, 0 }, { 1, 0, 0, 0 } };

b1 = 0x1010
b2 = 0x0010
b3 = 0x1000

~b1 & b2 = 0 b1がb2を支配
~b1 & b3 = 0 b1がb3を支配
~b2 & b3 != 0 b2はb3を支配しない

こういうことなら、初めからb2,b3を除外して組み合わせを検討すれば良い
(&と|は間違いやすいので要注意です）^でもよかった。

Answer 1

質問例の組み合わせ数が変わるパターンだとその都度似た処理をコピーしなければならず効率が悪いので、一覧を作る部分から作り直しました。
ただビット演算を使う方が楽なためint配列をString文字列に置き換えて処理しています。
外部からint配列で引数が渡されるとかいう場合、String文字列に置き換える処理を入れて下さい。

支配関係の除外は現在の処理の場合、
高ランクから順番にしているため、必然的に下位ランクが後になるので、
新しく追加する物が既に一覧にある物の下位になるかどうかをチェックして
一覧に加えない方式で処理しています。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

public class NNN {

    static String projectA[] = { "1100", "1010", "0100" };
    static String projectB[] = { "1010", "0010", "0100" };
    static String projectC[] = { "0101", "0001", "1000" };

    static String projectALL[][] = { projectA, projectB, projectC };
    static String projectList[] = Arrays.stream(projectALL).flatMap(pl -> Arrays.stream(pl)).toArray(String[]::new);

    static int rProjectBin = Integer.parseInt("1111", 2);

    static String company[] = { "A社", "B社", "C社" };

    public static void main(String[] args) {
        List<String> indexStrList = createIndexStrList();
        sysoutResult(indexStrList);
    }

    public static List<String> createIndexStrList() {
        List<String> indexStrList = new ArrayList<>();
        for (int i = 0; i < projectList.length; i++) {
            String result = setIndexStrList(indexStrList, projectList[i], String.valueOf(i), i + 1);
            excludeDominance(indexStrList, result);
        }
        return indexStrList;
    }

    public static String setIndexStrList(List<String> indexStrList, String pProject, String indexStr, int idx) {
        int pBin = Integer.parseInt(pProject, 2);
        for (int i = idx; i < projectList.length; i++) {
            int cBin = Integer.parseInt(projectList[i], 2);
            // ビット演算xor
            int rBin = pBin ^ cBin;
            // ビット演算xorの結果にandで演算を行い、適用ビットと同じ値であれば適用された(0から1に変わった)ことになる
            if ((rBin & cBin) == cBin) {
                String addStr = indexStr + "," + i;
                // 演算結果が"1111"と同じ場合、結果を返す
                if (rBin == rProjectBin) {
                    return addStr;
                } else {
                    // 演算結果が"1111"でない場合、再帰で自己メソッドを呼び出す
                    String result = setIndexStrList(indexStrList, Integer.toBinaryString(rBin), addStr, i);
                    excludeDominance(indexStrList, result);
                }
            }
        }
        return null;
    }

    public static void excludeDominance(List<String> indexStrList, String addIndexStr) {
        // 支配関係にあるプロジェクトを除外する
        if (addIndexStr == null) {
            return;
        }
        if (indexStrList.isEmpty()) {
            indexStrList.add(addIndexStr);
            return;
        }
        String[] addIndexesStr = addIndexStr.split(",");
        // 会社数以上プロジェクトがある場合、複数の同じ会社が指定されているので支配関係不明としてチェックしない
        if (addIndexesStr.length > projectALL.length) {
            indexStrList.add(addIndexStr);
            return;
        }
        int[][] indexes = convertIndexesStr(addIndexesStr);
        // プロジェクトで会社の重複がある場合、複数の同じ会社が指定されているので支配関係不明としてチェックしない
        if (doubleCheck(indexes, -1)) {
            indexStrList.add(addIndexStr);
            return;
        }
        for (String listIndexStr : indexStrList) {
            String[] listIndexesStr = listIndexStr.split(",");
            int[][] listIndexes = convertIndexesStr(listIndexesStr);
            // 会社の数が同じ場合
            if (indexes.length == listIndexes.length) {
                boolean[][] bolLen = new boolean[indexes.length][2];
                for (int i = 0; i < indexes.length; i++) {
                    // 会社が同じ場合
                    if (indexes[i][0] == listIndexes[i][0]) {
                        bolLen[i][0] = true;
                    }
                    // 加えようとしている会社のランクIndexが既に一覧にある会社のランクIndex以上(ランク下位)の場合
                    if (indexes[i][1] >= listIndexes[i][1]) {
                        bolLen[i][1] = true;
                    }
                }
                // 会社数によりチェック用の配列を作成
                boolean[][] chkBol = IntStream.range(0, indexes.length)
                        .mapToObj(i -> new boolean[] {true, true}).toArray(boolean[][]::new);
                // チェック結果が全てtrue(会社の組み合わせが同じで、ランク下位以下)の場合
                if (Arrays.deepEquals(bolLen, chkBol)) {
                    // リストに加えず処理を終了(除外扱い)
                    return;
                }
            }
        }
        indexStrList.add(addIndexStr);
    }

    public static boolean dominanceCheck(List<String> indexStrList, String indexStr) {
        // 支配関係のチェックを行う
        String[] indexesStr = indexStr.split(",");
        // 会社数以上プロジェクトがある場合、複数の同じ会社が指定されているので支配関係不明としてチェックしない
        if (indexesStr.length > projectALL.length) {
            indexStrList.add(indexStr);
            return false;
        }
        int[][] indexes = convertIndexesStr(indexesStr);
        // プロジェクトで会社の重複がある場合、複数の同じ会社が指定されているので支配関係不明としてチェックしない
        if (doubleCheck(indexes, -1)) {
            indexStrList.add(indexStr);
            return false;
        }
        return true;
    }

    public static boolean doubleCheck(int[][] indexes, int argConpanyIdx) {
        // 一社で複数のプロジェクトがあるかどうかチェックする
        for (int[] indexe : indexes) {
            int conpanyIdx = indexe[0];
            boolean result = conpanyIdx == argConpanyIdx;
            if (!result) {
                return result;
            }
            return doubleCheck(indexes, conpanyIdx);
        }
        return false;
    }

    public static int[][] convertIndexesStr(String[] indexesStr) {
        // 会社名とランクをIndexに置き換え、会社が複数ある場合まとめる
        int[][] indexes = new int[indexesStr.length][2];
        for (int i = 0; i < indexesStr.length; i++) {
            String[] idxs = indexesStr[i].split(",");
            for (String index : idxs) {
                int projectSize = 0;
                for (int j = 0; j < projectALL.length; j++) {
                    String[] projects = projectALL[j];
                    for (int k = 0; k < projects.length; k++) {
                        if (Integer.parseInt(index) == projectSize + k) {
                            indexes[i] = new int[] {j, k};
                        }
                    }
                    projectSize += projects.length;
                }
            }
        }
        return indexes;
    }

    private static void sysoutResult(List<String> indexStrList) {
        // 結果をコンソールに出力する
        for (String indexStr : indexStrList) {
            System.out.println("-------------------------");
            String[] indexes = indexStr.split(",");
            for (String index : indexes) {
                int projectSize = 0;
                for (int i = 0; i < projectALL.length; i++) {
                    String[] projects = projectALL[i];
                    for (int j = 0; j < projects.length; j++) {
                        if (Integer.parseInt(index) == projectSize + j) {
                            System.out.println(
                                    company[i] + "の" + (j + 1) + "位のプロジェクト＝1");
                        }
                    }
                    projectSize += projects.length;
                }
            }
        }
    }
}

Comments

[reina1125]

yureighost さん
できました！本当にありがとうございます！！(ToT)

Answer 2

やりたいことは、以下の通りで実現できると思います

私が現状考えている方法としては下記です。

①配列を用意してそこに最初の解の順位を保存
②以降、既存の解と新規の解との順位を比較
----支配関係がある場合 ==>支配されている解を消去、新たな解を保存
----支配関係がない場合 ==>新たな解として保存
③保存されている解を出力

支配関係のチェックは、正直コメントのやりとり見てもあまりわからなかったので
サンプルをうまく修正してくれればと思います。

考え方だけ。

プロジェクトと順位を一意の文字列に変換します。
変換ルール
先頭１文字目は、成り立つプロジェクトの数
２文字目、Aプロジェクトの順位
３文字目、Bプロジェクトの順位
４文字目、Cプロジェクトの順位
※順位は１位：４点、２位：２点、３位：１点の合計

変換した文字列の各桁を見て、どちらか一方にのみ支配関係があれば、そのどちらか
なければないというのを表す関数を作ります。
※ここの評価方法がよくわからないので、直してください。

先頭１文字が一致しない場合、どちらも支配関係にない。
２文字目以降
第一引数（left）が大きい場合、isLeftをtrueに、第二引数が大きい場合、isRightをtrueに
最終的にどちらか”だけ”フラグがたっていたら、そのフラグに準じた値を返却

/*
 * PRJ評価文字列を作成
 * 各PRJの評価をABCの順に連結した文字列を返す。
 */
private static String toHyoukaStr(int... prjs) {
	int[] company = { 0, 0, 0 }; // {A社, B社, C社}
	int[] rank = { 4, 2, 1 }; // 順位の重みづけ 2位、3位の合計より1位を大きく

	for (int i = 0; i < prjs.length; i++) {
		company[prjs[i] / 3] += rank[prjs[i] % 3];
	}

	// int配列を文字列に変換{1,2,3} -> "123"
	String ret = "" + prjs.length + java.util.Arrays.stream(company).mapToObj(Integer::toString).collect(Collectors.joining());
	return ret;
}

/*
 * 支配されているかのチェック.
 *
 * @left 評価するprj順位文字列
 * @right 評価するprj順位文字列
 * @return 0 支配関係にない
 *         0より大きい left が right を支配している
 *         0より小さい left が right に支配されている
 */
private static int controlTo(String left, String right) {
	// 構成するプロジェクトの数が違う場合
	if(left.charAt(0) != right.charAt(0)) {
		return 0;
	}

	boolean isLeft = false;
	boolean isRight = false;
	// 先頭からプロジェクトごとの順位を確認
	for (int i = 0; i < left.length(); i++) {
		if (left.charAt(i) > right.charAt(i)) {
			isLeft = true;
		} else if (left.charAt(i) < right.charAt(i)) {
			isRight = true;
		} else {
			// same
		}
	}

	if (isLeft ^ isRight) {
		if (isLeft) {
			return 1; // left が right を支配している
		} else {
			return -1; // right が left を支配している
		}
	}

	// 支配関係にない
	return 0;
}

使い方

例えば(1){A社１位,B社１,C社１位}と(2){A社2位,B社１位,C社１位}の組み合わせがあった場合、

B社,C社の順位は同じ1位ですが、A社に関しては(1)が1位,(2)が2位なので
(2)の組み合わせは(1)の組み合わせに含まれている(=支配されている)と言います。

String kakko1 = toHyoukaStr(0, 3, 6); // (1){A社１位,B社１,C社１位}
String kakko2 = toHyoukaStr(1, 3, 6); // (2){A社2位,B社１位,C社１}

System.out.println("(1)が(2)を支配しているか？" + (controlTo(kakko1, kakko2) > 0)); // true

使い方２（配列の場合）

3レコード目、A社1位、B社2位、C社2位

5レコード目、A社２位、B社3位、C社2位
において、3レコード目は１レコード目に支配されているということになります。

※「5レコード目は3レコード目に支配されている」の誤字だと思ってますが・・・

int[] rec3 = {0, 4, 7}; // 3レコード目、A社1位、B社2位、C社2位
int[] rec5 = {1, 5, 7}; // 5レコード目、A社２位、B社3位、C社2位

System.out.println("3レコード目が5レコード目を支配しているか？" + (controlTo(toHyoukaStr(rec3), toHyoukaStr(rec5)) > 0)); // true
System.out.println("5レコード目が3レコード目に支配されているか？" + (controlTo(toHyoukaStr(rec5), toHyoukaStr(rec3)) < 0)); // true

こんな感じで比較して、ArrayListかなんかに評価文字列か、配列そのものを保存していけばよいかと思います。

が、まずは支配関係のチェックについての単純なif文なので、実装してもらうしかないですね。