1

3 つの数字のセットがあり、セット内の数字を別のセットと比較したいと考えています。つまり、最初のセットの各数値が、他のセットの少なくとも 1 つの数値よりも小さいということです。注意点として、最初のセットの次の数値は、2 番目のセットの別の数値より小さくなければなりません (つまり、{6,1,6} は {8,8,2} に対して機能しますが、{6,2,6 } に対して {8,8,2} はしません)。私は作業方法を持っていますが、それは力ずくで醜いです。

setA と setB があり、それぞれに要素 a、b、c があるとします。

if(setB.a < setA.a)
    if(setB.b < setA.b)
        if(setB.c < setA.c)
            return true;
    else if(setB.b < setA.c)
        if(setB.c < setA.b
            return true;

等々...

4

3 に答える 3

1

編集:これらのセットは 3 つの値でハードコードされているとあなたが言ったことに気付きました。これは、任意のサイズのセットに対する非常に一般的なアルゴリズムです。

3 つの値のセットの場合、セット要素の同じダンプと並べ替えを実行してから、次の操作を実行できます。

if(setB.a < setA.a)
    if(setB.b < setA.b)
        if(setB.c < setA.c)
            return true;
return false;

================================================== ====

一般的なアルゴリズム:

これは、これを行うためにすぐに思いつく最も効率的な方法です。

疑似コード（Javaよりもpythonic、申し訳ありません-コメントで説明してください）：

list l1 = set1.items() //get the items out
list l2 = set2.items()

l1 = sort(l1)
l2 = sort(l2) //sort the lists

int set2idx1 = l1[0].find_closest_greater_than_value(l2) //binary search or something
if set2idx1 exists:
    l2 = l2[set2idx1+1:] //in python this means l2 is reassigned to a subarray of l2 starting at set2idx1+1 going to the end of l2
else:
    return false

for(int i=1; i<l1.len; i++)
    int set2idxi = l1[i].find_closest_greater_than_value(l2) //binary search or something
    if set2idxi exists:
        l2 = l2[set2idxi+1:]
    else
        return false

return true

意味が分からない場合はコメントしてください

編集 編集:

利害関係者のための一般的なアルゴリズムの説明:

  1. セット要素を配列にダンプする
  2. それらの配列を並べ替えます
  3. 最初の配列を反復処理し、2 番目の配列に現在の値より大きい値があるかどうかを確認します。もしそうなら、その値のインデックスを取得し、そのインデックスを含むそれ以前のすべてを削除し、残ったものに 2 番目の配列変数を再割り当てします。
  4. そのような値が存在しない場合 (存在しないか、テストする値が不足しているため、false を返します)。それ以外の場合は、最後に true を返します。

ここでの考え方は、配列がソートされているため、2 番目の配列で一致した要素よりも大きい要素は、1 番目の配列でテストしている要素よりも大きいことがわかっているということです。したがって、低い値を切り取ることができます。また、同じ値を使用したくない場合は、見つけた値も切り取ることができます。false を返す場合は、array1 の数値がすべて array2 の数値よりも大きいため、または array1 の数値よりも大きい十分な数値が array2 になかったため、より大きな値がなかったことが原因であることがわかります。

于 2012-12-07T00:23:23.580 に答える
0

次の疑似コードはどうでしょうか。

Condition(A : Set, B : Set) : Bool =
    Let a := max(A), b := min(B) In
        // Namely, that each number in the first set is less than at least one number in the other set
        If a <= b Then
            // the next numbers in the first set must be less than a different number in the second set 
            Condition(without(A, a), without(B, b))
        Else
            False
        EndIf

without(A, a) は、集合 A から集合 {a} を引いたものを意味します。

于 2012-12-07T00:23:00.750 に答える
0

あなたの例には重複した要素が含まれているため、Lista よりもうまくいくようです。Set単に：

1) 2 つのリストを並べ替えます。

2) 最初と 2 番目のリストのサイズが等しくなるまで、2 番目のリストから最初のいくつかの要素を切り取ります。

3) for eachと直接比較list1[i]します。list2[i]i

コード：

import java.util.*;
class Main {
    public static void main (String[] args) {
        List<Integer> list1 = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();
        list1.add(3); list1.add(7); list1.add(7);
        list2.add(8); list2.add(8); list2.add(2); list2.add(1); list2.add(5);
        //algorithm:
        Collections.sort(list1);
        Collections.sort(list2);
        List<Integer> list3 = list2.subList(list2.size() - list1.size(), list2.size());
        System.out.println(list1.size() + " " + list3.size());
        boolean pass = true;
        for(int i = 0; pass && i < list1.size(); i++)
            if(list1.get(i) >= list3.get(i))
                pass = false;
        System.out.println(pass);
    }
}
于 2012-12-07T00:59:04.933 に答える