この問題は、私が取り組んで以来ずっと私を悩ませてきました。私は、特定の人々が彼らのペアに基づいて一緒に住んでいるかどうかを調べる方法を見つけようとしています。例、私はリストを与えられます：
X[] = guy1, guy2, guy3, guy4, guy5
このリストのすべての要素を比較して、少なくとも半分が同居しているかどうかを確認するためのD＆Cアルゴリズムが必要です。それらが一緒に住んでいるかどうかを調べるために、与えられた単純な関数があります：それらが一緒に住んでいるLivesTogether(x, y)場合はtrueを返し、そうでない場合はfalseを返します。
何か案は？
O（n）パフォーマンスを達成する唯一の方法-GPUでペアリングチェックを実行します。つまり、GPUの異なるスレッドとして、各人が他の人とは別にペアリングをチェックすることができます。各人を画像上のピクセルとして表すだけで、ピクセルシェーダー/計算シェーダー/CUDAタスク/OpenCLタスク/何でも/計算して出力します
次に、結果の画像をシステムメモリにアップロードし、CPUを使用して計算します。つまり、白いピクセルの量を計算します。原則として、このようなGPUタスクは線形時間で実行されます（ビデオメモリがすべてのピクセル（別名guys / dna）を保持するのに十分な大きさであると仮定します）。
これは、グアバを使用した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
}
あなたができることは、Divide and Conquer を使用してすべての可能なペア (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;
}
}
U は単に文字列配列を入力例として渡す必要があります: "A","B","C","D" このメソッドは、可能なすべてのペアの ArrayList を提供します。このリストを反復処理し、各ペアで LivesTogether を呼び出します。お役に立てれば！！
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)
わかりました、これがJavaでの私のソリューションであり、それを証明するための単体テストがあります（長さについて申し訳ありません）。これも実際には分割征服アルゴリズムではありませんが、guy1 が guy2 のルームメイトであるかどうかをチェックせず、guy2 が guy1 のルームメイトであるかどうかをチェックしないため、他の回答よりも効率的です。
およびメソッドは Eclipse によって生成され、my が正しく機能するために必要でしequals()た。hashCode()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());
}
}