分而治之 - 比较所有可能的组合

Question

自从我开始研究这个问题以来，这个问题就一直困扰着我。我正在尝试找出一种方法来根据某些人的配对来查明他们是否住在一起。例如，给我一个列表：

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

我需要一个 D&C 算法来比较该列表的所有元素，看看是否至少有一半元素生活在一起。为了查明他们是否住在一起，有一个简单的函数：LivesTogether(x, y)，如果他们住在一起，则返回 true，否则返回 false。

有什么想法吗？

Answer 1

好的，这是我的 Java 解决方案，并通过单元测试来证明它（抱歉有点长）。这也不是真正的分而治之算法，但它比其他答案更有效，因为它不会检查 Guy1 是否是 Guy2 的室友和检查 Guy2 是否是 Guy1 的室友。

equals() 和 hashCode() 方法由 Eclipse 生成，需要我的 HashSet 才能正常工作。

Guy.java：Roommates.java：RoommateFinder.java：RoommateFinderTest.java

import java.util.ArrayList;
import java.util.List;

public class Guy {
    String name;
    List<Guy> roommates;

    public Guy(String name) {
        this.name = name;
        this.roommates = new ArrayList<Guy>();
    }

    public boolean addRoommate(Guy roommate) {
        return this.roommates.add(roommate) && roommate.roommates.add(this);
    }

    public List<Guy> getRoommates() {
        return this.roommates;
    }

    public String getName() {
        return this.name;
    }

    public String toString() {
        return this.getName();
    }

    public boolean livesWith(Guy potentialRoommate) {
        return this.roommates.contains(potentialRoommate);
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (!(obj instanceof Guy)) {
            return false;
        }
        Guy other = (Guy) obj;
        if (name == null) {
            if (other.name != null) {
                return false;
            }
        } else if (!name.equals(other.name)) {
            return false;
        }
        return true;
    }

}

：

public class Roommates {
    private Guy guy1;
    private Guy guy2;

    public Roommates(Guy guy1, Guy guy2) {
        this.guy1 = guy1;
        this.guy2 = guy2;
    }

    public Guy getGuy1() {
        return this.guy1;
    }

    public Guy getGuy2() {
        return this.guy2;
    }

    public String toString() {
        return guy1 + " lives with " + guy2;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((guy1 == null) ? 0 : guy1.hashCode());
        result = prime * result + ((guy2 == null) ? 0 : guy2.hashCode());
        return result;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (!(obj instanceof Roommates)) {
            return false;
        }
        Roommates other = (Roommates) obj;
        if (guy1 == null) {
            if (other.guy1 != null) {
                return false;
            }
        } else if (!guy1.equals(other.guy1)) {
            return false;
        }
        if (guy2 == null) {
            if (other.guy2 != null) {
                return false;
            }
        } else if (!guy2.equals(other.guy2)) {
            return false;
        }
        return true;
    }
}

​

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class RoommateFinder {
    List<Roommates> roommates;
    List<Guy> guys;

    public RoommateFinder(List<Guy> guys) {
        this.roommates = new ArrayList<Roommates>();
        this.guys = guys;
        // clone the guys List because findRoommates is going to modify it
        List<Guy> cloneOfGuys = new ArrayList<Guy>();
        for (Guy guy : guys) {
            cloneOfGuys.add(guy);
        }
        this.findRoommates(cloneOfGuys);
    }

    private void findRoommates(List<Guy> guys) {
        Iterator<Guy> iter = guys.iterator(); 
        if (!iter.hasNext()) {
            return;
        }
        Guy firstGuy = iter.next();
        while (iter.hasNext()) {
            Guy potentialRoommate = iter.next();
            if (firstGuy.livesWith(potentialRoommate)) {
                Roommates roommates = new Roommates(firstGuy, potentialRoommate);
                this.roommates.add(roommates);
            }
        }
        guys.remove(firstGuy);
        this.findRoommates(guys);
    }

    public List<Roommates> getRoommates() {
        return this.roommates;
    }

    public List<Guy> getGuys() {
        return this.guys;
    }

    public int getUniqueGuyCount() {
        Set<Guy> uniqueGuys = new HashSet<Guy>();
        for (Roommates roommates : this.roommates) {
            uniqueGuys.add(roommates.getGuy1());
            uniqueGuys.add(roommates.getGuy2());
        }
        return uniqueGuys.size();
    }

    public boolean atLeastHalfLivingTogether() {
        return this.getUniqueGuyCount() * 2 >= this.guys.size(); 
    }
}

​

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.List;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

public class RoommateFinderTest {
    private List<Guy> guys;
    private Guy harry, larry, terry, barry, herbert;

    @Before
    public void setUp() throws Exception {
        harry = new Guy("Harry");
        larry = new Guy("Larry");
        terry = new Guy("Terry");
        barry = new Guy("Barry");
        herbert = new Guy("Herbert");

        harry.addRoommate(larry);
        terry.addRoommate(barry);

        guys = new ArrayList<Guy>();
        guys.add(harry);
        guys.add(larry);
        guys.add(terry);
        guys.add(barry);
        guys.add(herbert);
    }

    @After
    public void tearDown() throws Exception {
        harry = null;
        larry = null;
        terry = null;
        barry = null;
        herbert = null;
        guys = null;
    }

    @Test
    public void testFindRoommates() {
        RoommateFinder roommateFinder = new RoommateFinder(guys);
        List<Roommates> roommatesList = roommateFinder.getRoommates();
        Roommates[] expectedRoommates = new Roommates[] {
                new Roommates(harry, larry),
                new Roommates(terry, barry)
                };
        assertArrayEquals(expectedRoommates, roommatesList.toArray());
        assertTrue(roommateFinder.atLeastHalfLivingTogether());
    }
}

Answer 2

define a new collection of <guy,guy> tuples

foreach guy1 in the list
   foreach guy2 in the collection of guys positioned after guy1 in the list
       if guy1 != guy2 and LivesTogether(guy1, guy2) 
           then add <guy1, guy2> to collection

if the number of tuples in the collection is greater than 1/4 of the number of guys
    then at least half the guys are the collection (and therefore live together)

Answer 3

这是我使用 guava 的 java 解决方案，顺便说一下，它不是 D&C算法，但我想你会用这个得到答案：

Set<Set<Integer>> set=Sets.filter(Sets.powerSet(Sets.newHashSet(1,2,3,4,5)), new Predicate<Set<Integer>>() {
    @Override
    public boolean apply(Set<Integer> arg0) {
        if(arg0.size()==2)
         return true;
        return false;
    }
});

for(Set<Integer> s:set) {
    System.out.println(s);//use your function here
}

Answer 4

实现 O(n) 性能的唯一方法是在 GPU 上运行配对检查。也就是说，每个人都可以与其他人分开检查配对 - 作为 GPU 上的不同线程。只需将每个人表示为图像上的像素，然后编写像素着色器/计算着色器/CUDA 任务/OpenCL 任务/无论什么/，

• 如果图像中有任何配对，则计算并输出白色像素，
• 如果没有配对，则计算并输出黑色像素。

然后将生成的图像上传到系统内存，并使用 CPU 计算 - 你有多少白色像素。原则上，此类 GPU 任务将以线性时间运行（假设您的视频内存足够大，可以容纳所有像素（又名 Guys/DNA））。

Answer 5

我认为你可以做的是使用分而治之生成所有可能的对（n 选择 2），然后为生成的所有对调用函数 LivesTogether(x,y) 。
我可以给你分治算法来生成所有可能的对。

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;
          }
   }

您只需传递字符串数组作为输入示例：“A”，“B”，“C”，“D”，此方法将为您提供所有可能对的 ArrayList。现在迭代此列表并对每对调用 LivesTogether。希望这有帮助！

Answer 6

这是我的解决方案。其中包括按照以下步骤查找室友组：

1. 添加所有待访问的人
2. 遍历所有找到其各自室友的人
3. 如果一个人不再待访问，我们不需要获取该人的室友，因为它已经属于一个室友团体。
4. 验证找到的室友数量是否至少占所有人的 50%，如果是则返回 true，否则继续搜索下一组。
5. 重复 2-4，直到我们到达人员列表的末尾，
6. 因为任何组都满足 50% 标准，所以最后返回 false。

空间复杂度：O(n)。
时间复杂度：O(R*n)。
在哪里：
n 是人数（输入大小）
R 室友组的数量

最坏的情况是每个人单独居住，因此组的数量等于输入。运行时间复杂度为 O(n*n)

public boolean halfLiveTogether(String[] people) {
        if(people == null) {
            return false;
        }
        
        Set<String> toVisit = new HashSet<>();
        
        // start with all people to explore
        toVisit.addAll(Arrays.asList(people));
        
        for(String person : people) {
            
            if(toVisit.contains(person)) {
                
                int roommates = getRoommates(person, people, toVisit);
                
                if(roommates >= people.length / 2) {
                    return true;
                }
            }
        }
        
        return false;
    }
    

private int getRoommates(String roommate, String[] people, Set<String> toVisit) {
            
            int roommates = 0; // assuming liveTogether(x, x) returns true (a person is roommate with themself)
            
            List<String> toRemove = new ArrayList<>();
            
            for(String person : toVisit) {
                
                if(liveTogether(roommate, person)) {
                    
                    toRemove.add(person);
                    roommates++;
                }
            } 
            
            // we already found roommates group for these people, do not search here any more
            for(String remove : toRemove) {
                toVisit.remove(remove); 
            }
            
            return roommates;
        }