3

我正在创建一个程序，其中涉及一段代码，我需要从单个项目（名称）列表中选择对。

初始列表来自一个ArrayList<String>包含人的所有唯一名称的单一列表。

我的尝试如下：

//Performance is not really a focus as the lists are small (20 ~ 60 elements),
//thus I use a SecureRandom instead of a Random.
SecureRandom rnd = new SecureRandom();

//List of names
ArrayList<String> Names = new ArrayList<>();

//Names populated somewhere here..

//Make a secondary array which houses the available names...
ArrayList<String> AvailNames = new ArrayList<>();
AvailNames.addAll(Names);

LinkedHashMap<String, String> NamePair = new LinkedHashMap<>();
Iterator<String> Iter = Names.iterator();

// LOOP A
while(Iter.hasNext()){
    String name = Iter.next();
    int index;

   /*
    * LOOP B
    * Find a unique pair randomly, looping if the index is the same.
    * Not the most efficient way, but gets the job done...
    */
    while(true){
        index = rnd.nextInt(AvailNames.size());
        if(!AvailNames.get(index).equals(name)){
            break;
        }
    }

    NamePair.put(name, AvailNames.remove(index));
}

当名字的数量是奇数时，我遇到了LOOP B（见上文）无限期运行的问题。

我发现问题在于，有时，当所有对都被取走时，剩下的姓氏对是非唯一的，导致 if 语句永远不会为真。

以列表为例：

  1. 一个
  2. 乙
  3. C
  4. D
  5. 乙

程序在执行过程中，可能首先创建一个名称对，从 A 到 D 排序，如下所示：

  1. A - B
  2. B - C
  3. C - D
  4. D - C

它作为最后一对留下E - E，不允许作为一对（因为项目/名称不是唯一的）。由于配对分配是随机的，因此有时会起作用，有时会不起作用，坦率地说，这很烦人……

我确信解决方案非常简单，但由于某种原因，我似乎无法找到解决这个问题的方法。任何帮助表示赞赏。

4

3 回答 3

3

您可以检测到何时进入这种情况，只需将您的最后一个AvailName元素与一些随机选择的前一对元素的第二个元素交换即可。例如，如果您选择了第二对，则将其更改为 BE，而您的最后一对将是 EC。

这将始终给出两个对，每个对具有不同的第一个和第二个元素：所选对不能将 E 作为其第一个元素（您将生成唯一的对）或作为其第二个元素（否则 E 不会在AvailName）。

于 2013-11-09T12:04:32.693 回答
2

只是一个想法; 您可以计算所有可能的唯一对，然后从中随机抽样。

需要注意的是，这是 O(n 2 )，因此对于大量名称可能会变慢；而且新的List会变得相当大，因为它包含 n(n 2 -1)/2 个元素。

这是一个例子：

public static void main(String args[]) {
    final List<String> in = new ArrayList<String>() {
        {
            add("A");
            add("B");
            add("C");
            add("D");
            add("E");
        }
    };
    final List<String[]> pairs = new ArrayList<>();
    for (int i = 0; i < in.size(); ++i) {
        for (int j = i + 1; j < in.size(); ++j) {
            pairs.add(new String[]{in.get(i), in.get(j)});
        }
    }
    Collections.shuffle(pairs);
    for (final String[] pair : pairs) {
        System.out.println(Arrays.toString(pair));
    }
}

输出：

[B, E]
[A, C]
[A, E]
[A, B]
[B, D]
[C, D]
[C, E]
[B, C]
[A, D]
[D, E]

您创建一个新的List<String[]> pairs然后循环输入List。在每次迭代中，您都会遍历输入的其余部分 - 这可以保证您永远不会再次反转同一对。

一旦你填充了它，你就pairs可以简单shuffle地取走你想要的任意多对。鉴于Random来自均匀分布的样本，您最终应该以相同的概率在 中进行任何排序pairs。您也可以将您SecureRandom的方法传入其他shuffle方法。

于 2013-11-09T12:05:42.323 回答
0

可能类似于以下内容：

更新：

为了消除误解，以下代码将确保：

  • 独特的对
  • 以随机顺序

n!/(n-k)!假设源列表中没有重复的元素，您将拥有唯一的对，其中n是名称的数量，并且k是2我们正在创建的对。

创建唯一对后，我将它们打乱以获得随机性。

要使用更好的洗牌算法，Collections.shuffle(pairs, new SecureRandom())可以使用。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NamePairTest {


  private static class NamePair {
    private final String one;
    private final String two;

    public NamePair(String one, String two) {
      super();
      this.one = one;
      this.two = two;
    }


    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ((one == null) ? 0 : one.hashCode());
      result = prime * result + ((two == null) ? 0 : two.hashCode());
      return result;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      NamePair other = (NamePair) obj;
      if (one == null) {
        if (other.one != null) return false;
      } else if (!one.equals(other.one)) return false;
      if (two == null) {
        if (other.two != null) return false;
      } else if (!two.equals(other.two)) return false;
      return true;
    }

    @Override
    public String toString() {
      return one + " - " + two;
    }
  }


  public List<NamePair> createPairs(List<String> names) {
    List<NamePair> pairs = new ArrayList<>();
    // create all possible unique pairs, given the names list.
    for (String one : names) {
      for (String two : names) {
        // a pair must not have the same name twice
        if (!one.equals(two)) {
          NamePair newPair = new NamePair(one, two);
          // only add the pair if it is not already in the list of pairs.
          // this test will only be necessary if the names list contains duplicates.
          if (!pairs.contains(newPair)) pairs.add(newPair);
        } // if
      } // for
    } // for
    // now shuffle the list, as currently it is ordered.
    Collections.shuffle(pairs);
    return pairs;
  }


  public static void main(String[] args) {
    List<String> availableNames = Arrays.asList("A", "B", "C", "D", "E");
    NamePairTest namePairTest = new NamePairTest();
    for (NamePair pair : namePairTest.createPairs(availableNames)) {
      System.out.println(pair);
    }
  }

}
于 2013-11-09T12:33:00.600 回答