java - URL と文字列の可能なすべての組み合わせを作成します

Question

コンマで区切られた文字列のさまざまな組み合わせから URL を作成しようとしているので、それらの URL を使用してそれらを実行し、データを取り戻すことができます。

私はこのようなものを単純化しました。HashSetすべての文字列を含むがありますnot A,B,C in real。ここは簡単に変更しただけです。

Set<String> data = new HashSet<String>();
h.add("A");
h.add("B");
h.add("C");    

for (int i = 1; i < 1000; i++) {

String pattern = generateString(data);

String url = "http://localhost:8080/service/USERID=101556000/"+pattern;

System.out.println(url);

}

/**
 * Below is the method to generate Strings.
 /
private String generateString(HashSet<String> data) {

//not sure what logic I am supposed to use here?

}

したがって、出力は次のようになります-

http://localhost:8080/service/USERID=101556000/A
http://localhost:8080/service/USERID=101556000/B
http://localhost:8080/service/USERID=101556000/C
http://localhost:8080/service/USERID=101556000/A,B,C
http://localhost:8080/service/USERID=101556000/B,C
http://localhost:8080/service/USERID=101556000/C,A

--
And other combinations

上記の出力は、ランダムな順序でもかまいません。しかし、それはすべての可能な組み合わせでなければなりません。そして、すべての可能な組み合わせが終了したら、最初からやり直します。

上記の問題定義をどのように達成できますか?

score 3 · Accepted Answer

あなたが求めていることは些細なことではありません。

AとBの2本の弦を見てみましょう。

ここにすべての順列があります。

A
B
AB
BA

では、A、B、C の 3 つの弦を見てみましょう。

ここにすべての順列があります。

A
B
C
AB
AC
BA
BC
CA
CB
ABC
ACB
BAC
BCA
CAB
CBA

まだパターンが見えますか？

まず、単一の文字列順列をすべて見つける必要があります。次に、2 つの文字列順列。次に、3 つの文字列順列。など、文字列の数まで。

次に、順列のセット (2 つの文字列セットなど) 内で、可能なすべての順列を見つける必要があります。

これは Java ループで行うことができます。再帰を使用することもできます。

score 2 · Accepted Answer

k 配列 ( http://en.wikibooks.org/wiki/Probability/Combinatorics ) とは何かを考えると、k が 1 から D まで変化する k 配列 (D はデータコレクションのサイズ) を探しています。

これは計算することを意味します-私の最初の投稿では画像を投稿できないので、次の場所にある方程式を見てください:

それを行うために、k を変化させ、各 k の場合は n を変化させることができます (つまり、サブ配列またはデータのみを処理して k-順列を列挙します)。これらの k-順列は、再帰を使用して配列を左右に移動することで見つけることができます。

以下は、 whart is required を列挙することを証明する簡単なブートストラップです。

public class EnumUrl {

private Set<String> enumeration = null;
private List<String> data = null;
private final String baseUrl = "http://localhost:8080/service/USERID=101556000/";

public EnumUrl(List<String> d) {
    data = d;
    enumeration = new HashSet<String>(); // choose HashSet : handle duplicates in the enumeration process
}

public Set<String> getEnumeration() {
    return enumeration;
}

public static void main(String[] args) {

    List<String> data = new ArrayList<String>();
    data.add("A");
    data.add("B");
    data.add("C");

    EnumUrl enumerator = new EnumUrl(data);

    for (int k = 0; k < data.size(); k++) {

        // start from any letter in the set
        for (int i = 0; i < data.size(); i++) {
            // enumerate possible url combining what's on the right of indice i
            enumerator.enumeratePossibleUrlsToRight(data.get(i), i);

            // enumerate possible url combining what's on the left of indice i
            enumerator.enumeratePossibleUrlsToLeft(data.get(i), i);
        }

        // make a circular permutation of -1 before the new iteration over the newly combined data
        enumerator.circularPermutationOfData();
    }

    // display to syso
    displayUrlEnumeration(enumerator);
}

private void circularPermutationOfData() {
    String datum = data.get(0);
    for (int i = 1; i < data.size(); i++) {
        data.set(i - 1, data.get(i));
    }
    data.set(data.size() - 1, datum);
}

private static void displayUrlEnumeration(EnumUrl enumerator) {
    for (String url : enumerator.getEnumeration()) {
        System.out.println(url);
    }
}

private void enumeratePossibleUrlsToRight(String prefix, int startAt) {
    enumeration.add(baseUrl + prefix);
    if (startAt < data.size() - 1) {
        startAt++;
        for (int i = startAt; i < data.size(); i++) {
            int x = i;
            enumeratePossibleUrlsToRight(prefix + "," + data.get(x), x);
        }
    }
}

private void enumeratePossibleUrlsToLeft(String prefix, int startAt) {
    enumeration.add(baseUrl + prefix);
    if (startAt > 0) {
        startAt--;
        for (int i = startAt; i >= 0; i--) {
            int x = i;
            enumeratePossibleUrlsToLeft(prefix + "," + data.get(x), x);
        }
    }
}
}

{A,B,C} のプログラム出力:

http://localhost:8080/service/USERID=101556000/B,C
http://localhost:8080/service/USERID=101556000/B,A,C
http://localhost:8080/service/USERID=101556000/B,C,A
http://localhost:8080/service/USERID=101556000/B,A
http://localhost:8080/service/USERID=101556000/C
http://localhost:8080/service/USERID=101556000/B
http://localhost:8080/service/USERID=101556000/C,B,A
http://localhost:8080/service/USERID=101556000/A,C,B
http://localhost:8080/service/USERID=101556000/A,C
http://localhost:8080/service/USERID=101556000/A,B
http://localhost:8080/service/USERID=101556000/A,B,C
http://localhost:8080/service/USERID=101556000/A
http://localhost:8080/service/USERID=101556000/C,B
http://localhost:8080/service/USERID=101556000/C,A
http://localhost:8080/service/USERID=101556000/C,A,B

{A,B,C,D} の場合:

http://localhost:8080/service/USERID=101556000/B,A,D,C
http://localhost:8080/service/USERID=101556000/C,D
http://localhost:8080/service/USERID=101556000/A,D,C,B
http://localhost:8080/service/USERID=101556000/A,C,D
http://localhost:8080/service/USERID=101556000/D
http://localhost:8080/service/USERID=101556000/C
http://localhost:8080/service/USERID=101556000/A,C,B
http://localhost:8080/service/USERID=101556000/B
http://localhost:8080/service/USERID=101556000/A,B,C,D
http://localhost:8080/service/USERID=101556000/A,B,C
http://localhost:8080/service/USERID=101556000/D,C,B,A
http://localhost:8080/service/USERID=101556000/C,B,A,D
http://localhost:8080/service/USERID=101556000/A,B,D
http://localhost:8080/service/USERID=101556000/D,B
http://localhost:8080/service/USERID=101556000/D,C
http://localhost:8080/service/USERID=101556000/A
http://localhost:8080/service/USERID=101556000/D,C,A
http://localhost:8080/service/USERID=101556000/D,C,B
http://localhost:8080/service/USERID=101556000/C,D,A
http://localhost:8080/service/USERID=101556000/C,D,B
http://localhost:8080/service/USERID=101556000/D,A
http://localhost:8080/service/USERID=101556000/A,D,C
http://localhost:8080/service/USERID=101556000/A,D,B
http://localhost:8080/service/USERID=101556000/C,B,D
http://localhost:8080/service/USERID=101556000/B,A,D
http://localhost:8080/service/USERID=101556000/B,C
http://localhost:8080/service/USERID=101556000/B,A,C
http://localhost:8080/service/USERID=101556000/B,C,A
http://localhost:8080/service/USERID=101556000/B,A
http://localhost:8080/service/USERID=101556000/B,C,D
http://localhost:8080/service/USERID=101556000/C,B,A
http://localhost:8080/service/USERID=101556000/A,D
http://localhost:8080/service/USERID=101556000/D,A,B
http://localhost:8080/service/USERID=101556000/A,C
http://localhost:8080/service/USERID=101556000/D,A,C
http://localhost:8080/service/USERID=101556000/B,C,D,A
http://localhost:8080/service/USERID=101556000/A,B
http://localhost:8080/service/USERID=101556000/B,D
http://localhost:8080/service/USERID=101556000/C,D,A,B
http://localhost:8080/service/USERID=101556000/D,A,B,C
http://localhost:8080/service/USERID=101556000/D,B,A
http://localhost:8080/service/USERID=101556000/D,B,C
http://localhost:8080/service/USERID=101556000/B,D,A
http://localhost:8080/service/USERID=101556000/C,B
http://localhost:8080/service/USERID=101556000/C,A,D
http://localhost:8080/service/USERID=101556000/C,A
http://localhost:8080/service/USERID=101556000/B,D,C
http://localhost:8080/service/USERID=101556000/C,A,B

これは網羅的な列挙ではありません。基本的に、次のものが必要です。

（私の最初の投稿では、返信にある方程式を見るために画像を投稿することはできません.2つのリンクを投稿するという評判はありません... #omg）

これにより、64 個のコンビナゾンが作成され、次のように分散されます。

1 要素の 4 つの組み合わせ (k=1)
12元素の12の組み合わせ（k=2）
24 元素の 24 の組み合わせ (k=3)
24 元素の 24 の組み合わせ (k=4)

私のプログラムは k=1、k=2、k=3 で問題ないことがわかります。しかし、k=4 の組み合わせは 24 通りありません。プログラムを完成させるには、循環順列以外のデータのシャッフルについても繰り返す必要があります。実際、k=4 の場合、循環置換は入力データとしてインスタンス ADBC を生成しません (したがって、たとえば、私の実装では DBCA を生成できません)。この場合、可能なすべての順序で n 個の要素を持つすべての可能なデータ入力配列を列挙する必要があります。これは、k=n の場合の k-順列の特殊なケースであり、したがってn!順列を見つけることにつながります。n!これは、可能な順列ごとに EnumUrl メソッドを呼び出すことで実現できます。

これについては、それに応じて更新する必要がありますがEnumUrl enumerator = new EnumUrl(data);、私はあなたにいくつかの作業を任せていると思います:-)

HTH

score 1 · Accepted Answer

グアバを使用したジェネリックスを使用した任意のセットサイズで機能する短いバージョン、およびここに示す順列の方法。

基本的に、アイデアは次のとおりです。

パワーセットを生成し、空のセットを破棄します

べき集合の各セットについて、すべての順列を生成します

パブリッククラスQuickEnumeration{

Set<T> objects;

public QuickEnumeration(Set<T> objects) {
    this.objects = objects;
}

public List<List<T>> generateEnumeration() {
    List<List<T>> result = new ArrayList<List<T>>();
    // Compute the powerset
    Set<Set<T>> powerset = Sets.powerSet(objects);
    for (Set<T> set : powerset) {
        // Discard empty set
        if (set.size() > 0) {
            // Arraylist faster for swapping
            ArrayList<T> start = new ArrayList<T>(set);
            permute(start, 0, result);
        }
    }
    return result;
}

private void permute(ArrayList<T> arr, int k, List<List<T>> result) {
    for (int i = k; i < arr.size(); i++) {
        java.util.Collections.swap(arr, i, k);
        permute(arr, k + 1, result);
        java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() - 1) {
        result.add((List<T>) arr.clone());
    }
}

public static void main(String[] args) {
    Set<String> testSet = new HashSet<>();
    testSet.add("A");
    testSet.add("B");
    testSet.add("C");
    QuickEnumeration<String> enumerate = new QuickEnumeration<>(testSet);
    System.out.println(enumerate.generateEnumeration());
}

}

「A」、「B」、「C」でテストすると、次のようになります。

[[A], [B], [A, B], [B, A], [C], [A, C], [C, A], [B, C], [C, B], [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, B, A], [C, A, B]]

score 0 · Accepted Answer

あなたが本当に何を望んでいるのか完全にはわからないので、私はあなたのためにこのコードを書くことになりました. それがあなたを始めてくれることを願っています!

public static void doThis() {

    String url1="http://www.example.com";
    String string1="A";
    String url2="http://www.foo.com";
    String string2="B";
    String url3="http://www.bar.com";
    String string3="C";

    Map<String, String> abbrMap = new HashMap<String, String>();
    abbrMap.put(string1, url1);
    abbrMap.put(string2, url2);
    abbrMap.put(string3, url3);
    String string = string1+string2+string3;
    for(Map.Entry<String, String> m : abbrMap.entrySet()) {
        arrange(string, m.getValue());
    }

}

private static void arrange(String str, String url) {
    if (str.length()==0) return;
    StringBuffer sbuf = new StringBuffer();
    for (int j=0; j<str.length(); j++) {

        for(int i=j; i<str.length(); i++) {
            char c = str.charAt(i);
            sbuf.append(c);
            System.out.println(url+"/"+sbuf.toString());
            sbuf.append(",");
        }
        sbuf.setLength(0);
    }
}

出力：

http://www.example.com/A
http://www.example.com/A,B
http://www.example.com/A,B,C
http://www.example.com/B
http://www.example.com/B,C
http://www.example.com/C
http://www.foo.com/A
http://www.foo.com/A,B
http://www.foo.com/A,B,C
http://www.foo.com/B
http://www.foo.com/B,C
http://www.foo.com/C
http://www.bar.com/A
http://www.bar.com/A,B
http://www.bar.com/A,B,C
http://www.bar.com/B
http://www.bar.com/B,C
http://www.bar.com/C

java - URL と文字列の可能なすべての組み合わせを作成します

4 に答える 4

Related

Reference