1

自从我一直在研究这个问题以来，这个问题一直困扰着我。我试图找出一种方法来确定某些人是否根据他们的配对生活在一起。例如，我得到一个列表：

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

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

有任何想法吗？

4

6 回答 6

0 
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)
于 2010-12-09T03:25:58.457 回答
0

这是我在 java 中使用guava的解决方案，顺便说一下，它不是 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
}
于 2010-12-09T07:51:56.937 回答
0

好的，这是我在 Java 中的解决方案，并带有一个单元测试来证明它（对不起长度）。这也不是真正的分治算法，但它比其他答案更有效，因为它不检查 Guy1 是否是 Guy2 的室友，也不检查 Guy2 是否是 Guy1的室友。

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

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

}

Roommates.java：

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

RoommateFinder.java：

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

RoommateFinderTest.java：

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());
    }
}
于 2010-12-09T04:38:08.723 回答
0

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

  • 如果图像中有任何配对，则为白色像素，或
  • 黑色像素 - 如果它没有配对。

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

于 2010-12-10T12:10:16.350 回答
0

我认为你可以做的是使用分而治之生成所有可能的对（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。希望这可以帮助！！

于 2012-09-17T08:54:25.327 回答
0

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

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

空间复杂度：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;
        }
于 2020-07-12T18:38:50.370 回答