分而治之 - 比较所有可能的组合 [英] Divide and Conquer - Comparing all possible combinations

问题描述

此问题已被窃听我自从我一直在努力。我试图想出一个办法，以找出是否某些人生活在一起基于他们对。比如我是给一个列表：

This problem has been bugging me ever since I have been working on it. I am trying to figure out a way to find out if certain people live together based on their pairs. Example, I am given a list:

X[] = guy1, guy2, guy3, guy4, guy5

我需要A D和C算法来比较这个列表中的所有元素，看看是否至少有一半生活在一起。要看看他们住在一起，给出一个简单的函数： LivesTogether（X，Y）如果他们返回true，否则为false

I need a D&C algorithm to compare all elements of this list to see if at least half are living together. To find out if they live together, there is a simple function given: LivesTogether(x, y) that returns true if they do, false otherwise.

任何想法？

推荐答案

我想ü可以做的是产生所有可能的对（正选2）采用分而治之，然后调用函数LivesTogether（X，Y）的所有对生成的。 我可以给ü分而治之算法生成所有可能的对。

I think what u can do is generate all possible pairs (n choose 2) using Divide and Conquer, and Then call the function LivesTogether(x,y) for all pairs generated. I can give u Divide and Conquer algorithm to generate all possible pairs.

public ArrayList<String> genPairs(String s[])
   {
        if(s.length<2)
          {
             System.out.println("No Pairs possible");
             return null;
          }

         if(s.length==2)
          {
            ArrayList<String> result=new ArrayList<String>();
            result.add(s[0]+s[1]);
            return result;
          }

          else
          {
              String x=s[s.length-1];
              String s1[]=new String[s.length-1];
              for(int i=0;i<s.length-1;i++)
                 s1[i]=""+s[i];

              ArrayList<String> sub=genPairs(s1);
              ArrayList<String> result=new ArrayList<String>();
              result.addAll(sub);
              for(int i=0;i<s1.length;i++)
                {
                     result.add(s1[i]+x);
                }
                return result;
          }
   }

U的只需要通过字符串数组作为输入例如：A，B，C，D，这方法给ü对所有可能的ArrayList。现在通过这个列表循环，并呼吁LivesTogether上的一对。希望这有助于！

U simply need to pass the String array as input example: "A","B","C","D" and this method will give u an ArrayList of all possible pairs. Now iterate through this list and call LivesTogether on each pair. Hope this helps!!

这篇关于分而治之 - 比较所有可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！