Сопряжение среди членов в том же списке в java

Question

В описании проблемы у меня есть число «n» с числом членов «n».

например:

John jane (family 1) 
tiya (family 2) 
Erika (family 3) 

Я должен назначить всех членов таким образом, что человек не должен спариваться с членом его семьи. и вывод должен быть:

John => tiya 
jane => Erika 
tiya => jane 
Erika => john 

Я создал объект Person(name ,familyID, isAllocated). Создал список и добавил personName_id в этом.

Я собираюсь использовать карту для объединения. Так что john_1 будет ключевым, а tiya_2 будет стоить.

Я не могу связать эти пары через карту. Как я могу перетасовать элементы списка.

Также было бы неплохо, если бы кто-нибудь мог предложить мне лучшее решение.

Код:

Получение лицо:

public static List getperson() 
{ 
    Scanner keyboard = new Scanner(System.in); 
    String line = null; 
    int count = 0; 

    List <Person> people = new ArrayList<>(); 

    while(!(line = keyboard.nextLine()).isEmpty()) { 
     String[] values = line.split("\\s+"); 
     //System.out.print("entered: " + Arrays.toString(values) + "\n"); 
     int familyid = count++; 
     for(String name :values) 
     { 
     Person person = new Person(); 
     person.setFamilyId(familyid); 
     person.setName(name); 
     person.setAllocated(false); 

     people.add(person); 
     } 
    } 
    return people; 
} 

Mapping:

public static List mapGifts(List pesonList) 
{ 
    Map<String , String> personMap = new HashMap<String , String>(); 

    Iterator<Person> itr = pesonList.iterator(); 
    Iterator<Person> itr2 = pesonList.iterator(); 
    List<String> sender = new ArrayList<>(); 

    while(itr.hasNext()) 
     { 
      Person p = itr.next(); 

       sender.add(p.getName()+"_"+p.getFamilyId()); 
       personMap.put(p.getName()+"_"+p.getFamilyId(), ""); 
      // p.setAllocated(true); 

     } 

      while(itr2.hasNext()) 
      { 
       /*if(p.isAllocated()) 
       {*/ 

       // Separate Sender name and id from sender list 
       //check this id match with new p1.getFamilyId() 

       for(String sendername :sender) 
       { 
       // System.out.println("Sender "+sendername); 
        personMap.put(sendername, ""); 

       String[] names = sendername.split("_"); 
       String part1 = names[0]; // 004 
       String familyId = names[1]; // 004 


       Person p2 = itr2.next(); 
       System.out.println(p2.getFamilyId() +" "+familyId +" "+p2.isAllocated()); 

       if(p2.isAllocated()) 
       { 
        for (String value: personMap.values()) { 
         if (value != sendername) { 

         } 
        } 

       } 
       if(p2.getFamilyId() != Integer.parseInt(familyId)) 
       { 

       // add values in map 
       } 
       } 

       break; 
      // Person newPerson = personLists.get(j); 

      } 

    for (Iterator it = personMap.entrySet().iterator(); it.hasNext();) 
    { 
      Map.Entry entry = (Map.Entry) it.next(); 
      Object key = entry.getKey(); 
      Object value = entry.getValue(); 

      System.out.println("Gifts "+key+"=>"+value); 
     } 
    return pesonList; 
} 

Благодаря

Answer 1

Из того, что я читал, вы только все равно, что вы подходите людей , То, как они совпадают, не имеет значения. Тем не менее, я предполагаю, что у вас есть список FamilyID и список имен всех, и что вы можете отсортировать список людей в соответствии с семейными идентификаторами.

Давайте назовем их:

List<FamilyID> families; и LinkedList<Person> people; соответственно. (Вы можете сделать FamilyID перечислимым классом)

Нам нужны два хэшмапа. Один для создания списка (по существу списка смежности) членов семьи полученных им familyID:

HashMap<FamilyID, List<Person>> familyMembers;,

и один, чтобы создать список отправителя (ключ) и приемник (значение) пар:

HashMap<Person, Person> pairs;

Полезной функцией может быть то, что при предоставлении человеку и их семейному удостоверению мы можем найти следующего доступного человека, который может получить от них.

String generateReceiver(Person newSender, FamilyID familyID);

Реализация этого метода должно быть довольно просто. Вы можете перебирать список людей и проверять, не является ли текущий человек членом семьи. Если это условие проходит, вы удаляете их из списка «people», чтобы вы не пытались повторить их снова. Если вы используете связанный список для этого, удаление - O (1), так как у вас уже есть ссылка.В худшем случае при обходах список равен n + n - 1 + ... + 2 раза, чтобы получить эффективность времени O (n^2) (т. Е. У вас есть одно большое семейство и многие маленькие). Работайте над этим, чтобы выровнять LinkedList, использовать список на основе массива и сохранить отдельный массив значений индекса, соответствующий каждому «доступному в настоящее время получателю определенного семейства». Вы должны инициализировать эти значения, когда вы добавили людей из каждой семьи в список людей (т. Е. Начало семейства 1 - это индекс «0», если в семье 1 есть 2 человека, начало семьи 2 будет индексом «2»). Это сделало бы функцию O (1) раз, если бы вы только увеличивали текущий доступный индекс приемника каждый раз, когда вы добавили пару отправителя-получателя. (Сообщите мне, если вы хотите получить более подробную информацию об этом!)

Последнее, но не менее важное: цикл делает это для всех людей.

for (List<Person> family : familyMembers) 
    for (Person person : family) 
    { 
    // get the next available receiver who is not a family member 
    // add the family member and its receiver to "pairs" hash 
    } 

Обратите внимание, что вышеуказанный цикл является псевдокодом. Если вам интересно, если вы создадите конфликтующие приемники/отправители с помощью этого метода, вы не будете. Список людей в основном действует как список получателей. Каким бы способом вы не реализовали список people, generateReceiver(...) устраняет вероятность того, что алгоритм увидит неисправный приемник. Для эффективности, если вы выполняете реализацию на основе массива, вы находитесь в O (N) времени для генерации всех значений пары, где N - общее количество людей. Сама программа также будет O (N).

Конечно, все это основано на предположении, что у вас достаточно людей для соответствия парам отправителей-получателей. Вам нужно будет добавить колокола и свистки, чтобы проверить наличие особых случаев.

Надеюсь, это поможет! Удачи!