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

Хорошо, вот мое решение на Java с модульным тестом, чтобы доказать это (извините за длину). Это также не совсем алгоритм «разделяй и властвуй», но он более эффективен, чем другой ответ, поскольку он не проверяет, является ли парень1 соседом по комнате парня2, и проверяет, является ли парень2 соседом по комнате парня1.

Методы 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());
    }
}

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

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

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

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

Я думаю, что вы можете сделать, это сгенерировать все возможные пары (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;
          }
   }

Вам просто нужно передать массив String в качестве примера ввода: «A», «B», «C», «D», и этот метод даст вам ArrayList всех возможных пар. Теперь пройдитесь по этому списку и вызовите LivesTogether для каждой пары. Надеюсь это поможет!!

Вот мое решение. Который состоит в поиске групп соседей по комнате, выполнив следующие действия:

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