0

我正在尝试从用逗号分隔的不同字符串组合创建一个 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

上述输出也可以是任何随机顺序。但它应该是所有可能的组合。如果所有可能的组合都完成了，那么重新开始。

任何建议如何实现上述问题定义？

4

4 回答 4

3

你问的不是小事。

让我们看一下 2 个字符串，A 和 B。

这里是所有的排列。

A
B
AB
BA

好的，让我们看看 3 个字符串，A、B 和 C。

这里是所有的排列。

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

你看到模式了吗？

首先，您必须找到所有单个字符串排列。然后是两个字符串排列。然后是三个字符串排列。依此类推，直到字符串的数量。

然后，在一组排列（如两个字符串集）中，您必须找到所有可能的排列。

你可以用java循环来做到这一点。您也可以使用递归。

于 2013-02-15T01:39:45.657 回答
2

鉴于什么是 k 排列（http://en.wikibooks.org/wiki/Probability/Combinatorics），您正在寻找 k 从 1 到 D 变化的 k 排列，其中 D 是数据集合的大小。

这意味着要计算 - 我的第一篇文章我无法发布图片，所以请查看位于的等式：

为了做到这一点，您可以使 k 变化，并且对于每个 k 可能 n 变化（即仅处理子数组或数据以枚举 k 排列）。这些 k 排列可以通过使用递归将数组向右和向左移动来找到。

这是一个快速引导程序，可以证明需要枚举什么：

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 排列的一种特殊情况，其中 k=n，因此会导致找到n!排列。n!我们可以通过为每个可能的排列调用 EnumUrl 方法来实现这一点。

为此，您应该EnumUrl enumerator = new EnumUrl(data);相应地更新，但我想我会让您做一些工作:-)

高温高压

于 2013-02-15T09:30:43.943 回答
1

一个适用于任意集合大小的简短版本，使用泛型，使用guava以及此处给出的排列方法。

基本上这个想法如下：

  1. 生成幂集，丢弃空集

  2. 对于每组幂集，生成所有排列

    公共类 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]]
于 2013-02-17T12:31:47.197 回答
0

我不完全确定您真正想要什么，所以我最终为您编写了这段代码。希望它能让你开始！

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
于 2013-02-15T02:25:13.257 回答