Група пар значэнняў падлучаных у спісы

Таму я працую над праблемай, і, падышоўшы да сцяны, што я не магу здацца, каб знайсці шлях вакол. Я атрымліваю так шмат інфармацыі ад АС, што я думаў, я хацеў бы спытаць тут, і паглядзець, калі ёсць спосаб зрабіць гэта лепш, чым тое, што я ў пошуку. У прынцыпе, у мяне ёсць клас, які мае кучу значэнняў у ім, але для нашых мэтаў толькі адзін мае значэння.

   public class GroupPair
   {
       public string object1 { get; set; }
       public string object2 { get; set; }
       public List BothObjects
       {
           get
           {
               List s= new List();
               s.Add(object1);
               s.Add(object2);
               return s;
           }
  }

У мяне ёсць спіс, і мне трэба, каб мець магчымасць сартаваць іх у групы. Дзе гэта становіцца складаней, што абодва значэння не з'яўляюцца унікальнымі, і памер групы і колькасць груп з'яўляецца зменнымі. Я ў асноўным патрэбен спосаб, каб сказаць, "дайце мне кожную групу, якую можна зрабіць з гэтага спісу, дзе кожная група змяшчае ўсе пары, якія ўключаюць асобныя член групы.» Дазвольце мне прывесці і прыклад ... вось некаторыя пары:

a   d
f   h
d   t
n   w
h   a
n   o
q   d
w   f
o   y

Пасля групоўкі, гэта тое, што я хачу:

Group 1
a   d
h   a
q   d
f   h
w   f
d   t

Group 2
n   x
n   o
o   y

Падпаліць ваш мозг яшчэ? Любыя ідэі аб тым, як гэта магло быць зроблена, і нават калі ёсць назва для такога роду канцэпцыі, што я магу даследаваць сябе?

1
Гэта не сартаванне, гэта падключэнне да групоўкі.
дададзена аўтар RBarryYoung, крыніца
Гэта не сартаванне, гэта падключэнне да групоўкі.
дададзена аўтар RBarryYoung, крыніца
«Любыя ідэі аб тым, як гэта можна было б зрабіць», - не, не зусім. Ня, не ведаючы логікі для групоўкі і сартавання.
дададзена аўтар Oded, крыніца
«Любыя ідэі аб тым, як гэта можна было б зрабіць», - не, не зусім. Ня, не ведаючы логікі для групоўкі і сартавання.
дададзена аўтар Oded, крыніца
Гэта гучыць як тэорыі графаў. Вы маглі б быць лепш даследаваць некаторыя алгарытмы вызначэння маршруту і іх выкарыстання для стварэння груп. Нешта накшталт Дейкстров або Max Flow.
дададзена аўтар Haney, крыніца
Гэта гучыць як тэорыі графаў. Вы маглі б быць лепш даследаваць некаторыя алгарытмы вызначэння маршруту і іх выкарыстання для стварэння груп. Нешта накшталт Дейкстров або Max Flow.
дададзена аўтар Haney, крыніца
Прапанова: даведацца Linq. Гэта зробіць вашу жыццё прасцей і можа быць ключом, каб вырашыць вашу праблему. Акрамя таго, што сказаў @Oded.
дададзена аўтар Renan, крыніца
Прапанова: даведацца Linq. Гэта зробіць вашу жыццё прасцей і можа быць ключом, каб вырашыць вашу праблему. Акрамя таго, што сказаў @Oded.
дададзена аўтар Renan, крыніца
У выпадку, калі не група 1 і група 2 аб'яднання з-за агульны «вага»? Ці я скажаючы ваша ўяўленне аб групоўцы?
дададзена аўтар Chad, крыніца
У выпадку, калі не група 1 і група 2 аб'яднання з-за агульны «вага»? Ці я скажаючы ваша ўяўленне аб групоўцы?
дададзена аўтар Chad, крыніца
Можа быць, я не ясна? Логіка толькі фізічныя асобы. Група складаецца з усіх пар, якія ўключаюць у сябе ўвесь твар у групе. Напрыклад, у вышэйпаказанай групе 1, першая пара з'яўляецца і д, так што асобы, а і d. Толькі іншая пара, якая ўключае ў сябе гэтае і гадзіна, так што пара. Цяпер члены груп з'яўляюцца, д, і Н, так што група павінна ўтрымліваць ўсе пары, якія ўключаюць у сябе любыя з іх. І гэтак далей.
дададзена аўтар Levi Dempsey, крыніца
Можа быць, я не ясна? Логіка толькі фізічныя асобы. Група складаецца з усіх пар, якія ўключаюць у сябе ўвесь твар у групе. Напрыклад, у вышэйпаказанай групе 1, першая пара з'яўляецца і д, так што асобы, а і d. Толькі іншая пара, якая ўключае ў сябе гэтае і гадзіна, так што пара. Цяпер члены груп з'яўляюцца, д, і Н, так што група павінна ўтрымліваць ўсе пары, якія ўключаюць у сябе любыя з іх. І гэтак далей.
дададзена аўтар Levi Dempsey, крыніца
Ack, вы маеце рацыю, Чад! Я выправіць гэта.
дададзена аўтар Levi Dempsey, крыніца
Ack, вы маеце рацыю, Чад! Я выправіць гэта.
дададзена аўтар Levi Dempsey, крыніца

8 адказы

Вось мой хуткі і брудны падыход.

Кароткае тлумачэнне:
Ідэя складаецца ў тым, каб пачаць з адной парай (якія можна разглядаць як вузел у выглядзе графіка). З гэтага вузла, можна дадаць любыя суседнія вузлы (пары, якія маюць агульны элемент). Тады вы будзеце шукаць вузлы, якія прымыкаюць да тых вузлах, якія вы толькі што дадалі. Усе разам вы адсочваць, якія вузлы былі наведаны, так што вы не цыкл бясконца.

public static List> GetGroups(IEnumerable pairs)
{
   var groups = new List();

   var unassignedPairs = new HashSet(pairs);
   while (unassignedPairs.Count != 0)
   {
      var group = new HashSet();
      var rootPair = unassignedPairs.First();
      group.Add(rootPair);
      unassignedPairs.Remove(rootPair);

      var membersToVisit = new Queue(rootPair.BothObjects);
      var visited = new HashSet();
      while (members.Count != 0)
      {
         string member = membersToVisit.Dequeue();
         visited.Add(member);
         foreach (var newPair in unassignedPairs
                 .Where(p => p.BothObjects.Contains(member)).ToList())
         {
            group.Add(newPair);
            unAssignedPairs.Remove(newPair);
            foreach (var newMember in newPair.BothObjects.Except(visited))
            {
               membersToVisit.Enqueue(newMember)
            }
         }
      }
      groups.Add(group);
   }
   return groups;
}
1
дададзена

Вось мой хуткі і брудны падыход.

Кароткае тлумачэнне:
Ідэя складаецца ў тым, каб пачаць з адной парай (якія можна разглядаць як вузел у выглядзе графіка). З гэтага вузла, можна дадаць любыя суседнія вузлы (пары, якія маюць агульны элемент). Тады вы будзеце шукаць вузлы, якія прымыкаюць да тых вузлах, якія вы толькі што дадалі. Усе разам вы адсочваць, якія вузлы былі наведаны, так што вы не цыкл бясконца.

public static List> GetGroups(IEnumerable pairs)
{
   var groups = new List();

   var unassignedPairs = new HashSet(pairs);
   while (unassignedPairs.Count != 0)
   {
      var group = new HashSet();
      var rootPair = unassignedPairs.First();
      group.Add(rootPair);
      unassignedPairs.Remove(rootPair);

      var membersToVisit = new Queue(rootPair.BothObjects);
      var visited = new HashSet();
      while (members.Count != 0)
      {
         string member = membersToVisit.Dequeue();
         visited.Add(member);
         foreach (var newPair in unassignedPairs
                 .Where(p => p.BothObjects.Contains(member)).ToList())
         {
            group.Add(newPair);
            unAssignedPairs.Remove(newPair);
            foreach (var newMember in newPair.BothObjects.Except(visited))
            {
               membersToVisit.Enqueue(newMember)
            }
         }
      }
      groups.Add(group);
   }
   return groups;
}
1
дададзена

Гэты код адпавядае ўваходны выбарцы і выдае патрабаваны выхад. Bascially Я трымаю HashSet элементаў у групу і маю спіс remaing элементаў для апрацоўкі.

private static void GroupPairs(List> pairs)
{
    int groupCounter = 0;

    while (pairs.Count > 0)
    {
        var onegroup = new HashSet();
        Console.WriteLine("Group {0}", ++groupCounter);

        int initialGroupCount;
        do
        {
            var remainder = new List>();
            initialGroupCount = onegroup.Count;
            foreach (var curr in pairs)
            {
                if (onegroup.Contains(curr.Item1) ||
                    onegroup.Contains((curr.Item2)) ||
                    onegroup.Count == 0)
                {
                    Console.WriteLine("{0} {1}", curr.Item1, curr.Item2);
                    onegroup.Add(curr.Item1);
                    onegroup.Add(curr.Item2);
                }
                else
                {
                    remainder.Add(curr);
                }
            }
            pairs = remainder;
        } while (initialGroupCount < onegroup.Count);
    }
}
0
дададзена

Гэты код адпавядае ўваходны выбарцы і выдае патрабаваны выхад. Bascially Я трымаю HashSet элементаў у групу і маю спіс remaing элементаў для апрацоўкі.

private static void GroupPairs(List> pairs)
{
    int groupCounter = 0;

    while (pairs.Count > 0)
    {
        var onegroup = new HashSet();
        Console.WriteLine("Group {0}", ++groupCounter);

        int initialGroupCount;
        do
        {
            var remainder = new List>();
            initialGroupCount = onegroup.Count;
            foreach (var curr in pairs)
            {
                if (onegroup.Contains(curr.Item1) ||
                    onegroup.Contains((curr.Item2)) ||
                    onegroup.Count == 0)
                {
                    Console.WriteLine("{0} {1}", curr.Item1, curr.Item2);
                    onegroup.Add(curr.Item1);
                    onegroup.Add(curr.Item2);
                }
                else
                {
                    remainder.Add(curr);
                }
            }
            pairs = remainder;
        } while (initialGroupCount < onegroup.Count);
    }
}
0
дададзена

Для паўнаты карціны я таксама рэкурсіўнае рашэнне. Бліжэй да канца клас GroupPair, які дзейнічае як datacontainer з двума дапаможнымі метадамі: даданне і зліццё.

Вы выклічце яго наступным чынам:

var gp = GroupByPairs(
            new List>
                {
                    new Tuple("a", "d"),
                    new Tuple("f", "h"),
                    /*  you get the idea */
                }.GetEnumerator());

foreach (var groupData in gp)
{
    Console.WriteLine(groupData.ToString());
}

//recursive take on the problem
private static IEnumerable GroupByPairs(
    IEnumerator> pairs)
{
   //result Groups
    var listGroup = new List();
    if (pairs.MoveNext())
    {
        var item = pairs.Current;
        var current = new GroupPair(item);

        var subgroup = GroupByPairs(pairs);//recurse

       //loop over the groups
        GroupPair target = null;
        foreach (var groupData in subgroup)
        {
           //find the group the current item matches
            if (groupData.Keys.Contains(item.Item1) ||
                groupData.Keys.Contains(item.Item2))
            {
               //determine if we already have a target
                if (target == null)
                {
                   //add item and keep groupData
                    target = groupData;
                    groupData.Add(item);
                    listGroup.Add(groupData);
                }
                else
                {
                   //merge this with target
                   //do not keep groupData 
                    target.Merge(groupData);
                }
            }
            else
            {
               //keep groupData
                listGroup.Add(groupData);
            }
        }
       //current item not added
       //store its group in the listGroup
        if (target == null) 
        {
            listGroup.Add(current);    
        }
    }
    return listGroup;
}

public class GroupPair
{
    private static int _groupsCount = 0;
    private int id;

    public GroupPair(Tuple item)
    {
        id = Interlocked.Increment(ref _groupsCount);
        Keys = new HashSet();
        Items = new List>();
        Add(item);
    }

   //add the pair and update the Keys
    public void Add(Tuple item)
    {
        Keys.Add(item.Item1);
        Keys.Add(item.Item2);
        Items.Add(item);
    }

   //Add all items from another GroupPair
    public void Merge(GroupPair groupPair)
    {
        foreach (var item in groupPair.Items)
        {
            Add(item);
        }
    }

    public HashSet Keys { get; private set; }

    public List> Items { get; private set; }

    public override string ToString()
    {
        var build = new StringBuilder();
        build.AppendFormat("Group {0}", id);
        build.AppendLine();
        foreach (var pair in Items)
        {
            build.AppendFormat("{0} {1}", pair.Item1, pair.Item2);
            build.AppendLine();
        }
        return build.ToString();
    }
}
0
дададзена

Для паўнаты карціны я таксама рэкурсіўнае рашэнне. Бліжэй да канца клас GroupPair, які дзейнічае як datacontainer з двума дапаможнымі метадамі: даданне і зліццё.

Вы выклічце яго наступным чынам:

var gp = GroupByPairs(
            new List>
                {
                    new Tuple("a", "d"),
                    new Tuple("f", "h"),
                    /*  you get the idea */
                }.GetEnumerator());

foreach (var groupData in gp)
{
    Console.WriteLine(groupData.ToString());
}

//recursive take on the problem
private static IEnumerable GroupByPairs(
    IEnumerator> pairs)
{
   //result Groups
    var listGroup = new List();
    if (pairs.MoveNext())
    {
        var item = pairs.Current;
        var current = new GroupPair(item);

        var subgroup = GroupByPairs(pairs);//recurse

       //loop over the groups
        GroupPair target = null;
        foreach (var groupData in subgroup)
        {
           //find the group the current item matches
            if (groupData.Keys.Contains(item.Item1) ||
                groupData.Keys.Contains(item.Item2))
            {
               //determine if we already have a target
                if (target == null)
                {
                   //add item and keep groupData
                    target = groupData;
                    groupData.Add(item);
                    listGroup.Add(groupData);
                }
                else
                {
                   //merge this with target
                   //do not keep groupData 
                    target.Merge(groupData);
                }
            }
            else
            {
               //keep groupData
                listGroup.Add(groupData);
            }
        }
       //current item not added
       //store its group in the listGroup
        if (target == null) 
        {
            listGroup.Add(current);    
        }
    }
    return listGroup;
}

public class GroupPair
{
    private static int _groupsCount = 0;
    private int id;

    public GroupPair(Tuple item)
    {
        id = Interlocked.Increment(ref _groupsCount);
        Keys = new HashSet();
        Items = new List>();
        Add(item);
    }

   //add the pair and update the Keys
    public void Add(Tuple item)
    {
        Keys.Add(item.Item1);
        Keys.Add(item.Item2);
        Items.Add(item);
    }

   //Add all items from another GroupPair
    public void Merge(GroupPair groupPair)
    {
        foreach (var item in groupPair.Items)
        {
            Add(item);
        }
    }

    public HashSet Keys { get; private set; }

    public List> Items { get; private set; }

    public override string ToString()
    {
        var build = new StringBuilder();
        build.AppendFormat("Group {0}", id);
        build.AppendLine();
        foreach (var pair in Items)
        {
            build.AppendFormat("{0} {1}", pair.Item1, pair.Item2);
            build.AppendLine();
        }
        return build.ToString();
    }
}
0
дададзена

Гэта проста ідэя для вырашэння.

Вы павінны будзеце ведаць, колькі унікальных «індывіды» у вас ёсць. Для прыкладу, гэта 26.

Па-першае, стварыць слоўнік з 26 пар, дзе ключ з'яўляецца фізічная асоба, у нашым выпадку літара, а значэнне ўяўляе сабой нумар групы, дзе яна будзе ў рэшце рэшт. Для кожнай пары, пачатковае значэнне павінна быць роўна нулю.

Па-другое, вы захоўваеце цэлую зменную «groupNumber», які будзе захоўваць наступны нумар групы. Вы адфарматуйце яе з 1.

Затым вы ітэрацыю па спісе GroupPairs. Вы бераце першы GroupPair, які змяшчае «а» і «D» і ўсталяваць адпаведныя значэння ў слоўніку «1».

Для кожнага наступнага GroupPair вы бераце яго чалавек і шукаць адпаведныя значэння ў слоўніку.

Калі адно з значэнняў не роўная нулю, гэта значыць адзін з асоб, ужо належыць да групы, вы ўсталюеце іншае значэнне той самай даты, што ставіць яго ў той жа самай групе.

Калі абодва значэнні роўныя нулю вы ўсталюеце іх «groupNumber» і «прырашчэнне groupNumber».

Калі абодва значэнні роўныя нуля, то гэта, дзе гэта становіцца крыху больш складана. Вы знойдзеце ўсе пары ў слоўніку групы, дзе значэнне роўна другое значэнне з гэтай пары, і ўсталяваць іх значэнне для першага значэння з гэтай пары.

Пасля таго, як гэта будзе зроблена, вы ітэрацыя па спісе GroupPairs яшчэ раз. Для кожнай пары вы глядзіце на першы сінгл у слоўніку групы і такім чынам высветліць, да якой групы належыць пары.

Спадзяюся, што мае сэнс ...

0
дададзена

Гэта проста ідэя для вырашэння.

Вы павінны будзеце ведаць, колькі унікальных «індывіды» у вас ёсць. Для прыкладу, гэта 26.

Па-першае, стварыць слоўнік з 26 пар, дзе ключ з'яўляецца фізічная асоба, у нашым выпадку літара, а значэнне ўяўляе сабой нумар групы, дзе яна будзе ў рэшце рэшт. Для кожнай пары, пачатковае значэнне павінна быць роўна нулю.

Па-другое, вы захоўваеце цэлую зменную «groupNumber», які будзе захоўваць наступны нумар групы. Вы адфарматуйце яе з 1.

Затым вы ітэрацыю па спісе GroupPairs. Вы бераце першы GroupPair, які змяшчае «а» і «D» і ўсталяваць адпаведныя значэння ў слоўніку «1».

Для кожнага наступнага GroupPair вы бераце яго чалавек і шукаць адпаведныя значэння ў слоўніку.

Калі адно з значэнняў не роўная нулю, гэта значыць адзін з асоб, ужо належыць да групы, вы ўсталюеце іншае значэнне той самай даты, што ставіць яго ў той жа самай групе.

Калі абодва значэнні роўныя нулю вы ўсталюеце іх «groupNumber» і «прырашчэнне groupNumber».

Калі абодва значэнні роўныя нуля, то гэта, дзе гэта становіцца крыху больш складана. Вы знойдзеце ўсе пары ў слоўніку групы, дзе значэнне роўна другое значэнне з гэтай пары, і ўсталяваць іх значэнне для першага значэння з гэтай пары.

Пасля таго, як гэта будзе зроблена, вы ітэрацыя па спісе GroupPairs яшчэ раз. Для кожнай пары вы глядзіце на першы сінгл у слоўніку групы і такім чынам высветліць, да якой групы належыць пары.

Спадзяюся, што мае сэнс ...

0
дададзена