1. 首页
  2. 问答
  3. 使URL与字符串的所有可能的组合

使URL与字符串的所有可能的组合

2013-02-15 47 views
0

我想从逗号分隔的字符串的不同组合中创建一个url，以便我可以使用这些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

以上输出可以在任何随机顺序为好。但它应该是所有可能的组合。如果所有可能的组合都完成了，然后重新开始。

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

来源

2013-02-15 AKIWEB

+0

从我可以告诉，一个URL无关您的问题。你有一个Collection作为输入，你想排列所有的可能性。有很多关于如何在stackoverflow上做到这一点的文章。 – 2013-02-15 01:30:40

+1

你想排列或组合？无论哪种方式，请随时使用Google或SO搜索工具。此主题已在前面讨论过。 – 2013-02-15 01:45:10

+0

字符串与逗号之间的任何特定组合。因此，我可以将这些插入网址 – AKIWEB 2013-02-15 01:45:42

回答

2

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

这意味着计算 - 我的第一篇我不能发布图像所以看位于公式：

为了做到这一点，你可以让ķ有变动，以及对每个k可以变化（即，仅处理子数组或数据以列举k-排列）。这些k-排列可以通过使用递归将数组向右和向左移动来找到。

这里是一个快速的自举，证明枚举whart是必需的：

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个combinaisons，分布如下：1个元件（K = 1）12元件的

  • 12个combinaisons的

    • 4 combinaisons（K = 2）24元件（k的
    • 24个combinaisons = 3 ）
      • 24元件（K = 4）的
    • 24 combinaisons

    你可以看到，我的程序是对于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);据此，但我想我让一些对你的工作，使:-)

    HTH

    • 来源

    2013-02-15 09:30:43 Fafhrd

    +0

    第二个等式我无法张贴becasue作为一个新用户我没有“声誉”islocated在：http://i.stack.imgur.com/my6wv.gif – Fafhrd 2013-02-15 09:31:21

    3

    你问的是不平凡的。

    让我们看两个字符串，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-15 01:39:45

    +1

    虽然这个想法是相似的，但OP在文本中要求*组合*，并且尽管在方法名称中使用了“置换”一词。 – 2013-02-15 01:44:03

    +1

    我不同意。在他的输出示例中，CA是一个排列组合。 – 2013-02-15 01:46:56

    +0

    这取决于你是否将它解释为一个集合或一个列表。由于AC没有得到，我把它作为一个集合。 – 2013-02-15 02:36:52

    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-15 02:25:13 Prince

    +0

    一个地图似乎混淆了这个问题背后的组合思想...... – 2013-02-15 02:39:46

    +0

    就像我说的，从上面的问题中不清楚。 “他的意思是”“其他任何组合”？如果问题明确，组合的想法将会清晰。然后，这完全是关于逻辑。 – Prince 2013-02-15 03:18:56

    +0

    尽管问题不明，但我没有看到每个String和URL之间的明确关系，所以Map是不合适的。 – 2013-02-15 03:24:36

    1

    短版任意设定大小的工作，与仿制药，使用guava，以及排列方法given here。

    基本思路如下：

    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-17 12:31:47 Julien

    相关问题

     相关问题