I had a problem with permutations in an array.

There is an input array of categories {1, 2.1, 3, 4.1, 5.3} , 1 and 3 - these are parent categories, and 2.1 , 4.1 , 5.3 are, respectively, child categories.

It is necessary to make a permutation so that the original array looks like {1, 2.1, 4.1, 3, 5.3} regardless of the number of parent categories and children.

  • Which of the following languages? - br3t
  • On any of them - Nicholas
  • [5.1, 4, 3.2, 2, 1.1, 1].sort() good? - br3t
  • And what kind of data do you have? Strings? Classes? Real, God forbid, numbers? - VladD
  • [{id: 1, name: parent}, {id: 2, name: child, parent: 1}, {id: 3, name: parent 2}, {id: 4, name: child 2, parent: 1} , {id: 5, name: child 3, parent: 3}] - For example, what an array looks like. It is necessary that the child categories are located under their parent category. - Nicholas

1 answer 1

You basically need a sort of topological sort.

We use the standard method of merging lists. I write in C #, LinkedList cannot merge into it, so I wrote my bike.

Auxiliary classes:

 class LinkedNode<T> { public T Entry; public LinkedNode<T> Next; } class MergeableLinkedList<T> { public LinkedNode<T> First, Last; public MergeableLinkedList(T head) { First = new LinkedNode<T>() { Entry = head }; Last = First; } public void Merge(MergeableLinkedList<T> other) // other is destroyed { Last.Next = other.First; Last = other.Last; } }

Your data structure:

 class Entry { public int id; public int? parent; }

Data:

 var data = new Entry[] { new Entry() { id = 1 }, new Entry() { id = 2, parent = 1 }, new Entry() { id = 3 }, new Entry() { id = 4, parent = 1 }, new Entry() { id = 5, parent = 3 }, new Entry() { id = 6, parent = 4 } };

Sorting:

 // создаём списки var lists = new Dictionary<int, MergeableLinkedList<Entry>>(); foreach (var d in data) lists[d.id] = new MergeableLinkedList<Entry>(d); // сливаСм ΠΈΡ… foreach (var d in data) { // Ссли Π΅ΡΡ‚ΡŒ ΠΏΡ€Π΅Π΄ΠΎΠΊ... if (d.parent != null) { var parentId = d.parent.Value; // свой список подцСпляСм Π² ΠΊΠΎΠ½Π΅Ρ† списка ΠΏΡ€Π΅Π΄ΠΊΠ° lists[parentId].Merge(lists[d.id]); lists[d.id] = lists[parentId]; } } // ΠΈ ΠΏΠ΅Ρ€Π΅ΠΏΠ°ΠΊΠΎΠ²Ρ‹Π²Π°Π΅ΠΌ всё Π² Π½ΠΎΠ²Ρ‹ΠΉ массив var newData = new Entry[data.Length]; var newDataIndex = 0; foreach (var d in data) { if (d.parent == null) { for (var curr = lists[d.id].First; curr != null; curr = curr.Next) newData[newDataIndex++] = curr.Entry; } }

Conclusion:

 foreach (var d in newData) { if (d.parent != null) Console.Write(d.parent + "."); Console.WriteLine(d.id); }

Result:

 1 1.2 1.4 4.6 3 3.5