Разделяй и властвуй - сравнивая все возможные комбинации

Question

Эта проблема беспокоила меня с тех пор, как я над ней работаю. Я пытаюсь найти способ выяснить, живут ли определенные люди вместе на основе их пар. Пример, мне дают список:

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

Мне нужен алгоритм D & C, чтобы сравнить все элементы этого списка, чтобы увидеть, живут ли хотя бы половина из них вместе. Чтобы выяснить, живут ли они вместе, есть простая функция: LivesTogether(x, y), которая возвращает true, если они это делают, иначе false.

Есть идеи?

Answer 1

Я думаю, что вы можете сделать, это сгенерировать все возможные пары (n выберите 2), используя Divide и Conquer, а затем вызвать функцию 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 просто нужно передать массив String в качестве входного примера: «A», «B», «C», «D», и этот метод даст вам ArrayList всех возможных пар. Теперь переберите этот список и вызовите LivesTogether для каждой пары. Надеюсь, это поможет !!

Answer 2

Единственный способ добиться производительности O (n) - запустить проверку сопряжения на графическом процессоре.То есть каждый парень может сделать это, проверяя пары отдельно от других - как разные потоки на GPU.Просто представьте каждого парня в виде пикселя на изображении и напишите пиксельный шейдер / вычислительный шейдер / задание CUDA / задание OpenCL / что угодно / которое вычисляет и выводит

• белый пиксель, если в изображении есть какие-либо пары, или1004 *
• черный пиксель - если у него нет пар.

Затем загрузите полученное изображение в системную память и рассчитайте с помощью процессора - сколько у вас белого пикселя.В принципе, такая задача графического процессора будет выполняться за линейное время (при условии, что ваша видеопамять достаточно велика, чтобы вместить все пиксели (так называемые парни / днк)).

Answer 3

Хорошо, вот мое решение на 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());
    }
}

Answer 4

Это мое решение в 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
}

Answer 5

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)