Customized Reordering/Sorting of a List in Perl in O(n)

Question

I am re-ordering a list.

My OrignalList, INPUT: @lineItems

[
  {id=> 'id1', ..},
  {id=> 'id2', 'groupId'=>45D,.. },
  {id=> 'id3', 'groupId'=>56A, .. },
  {id=> 'id4', 'groupId'=>45D, 'isParent'=>1 .. },
  {id=> 'id5', ..},
  {id=> 'id6', 'groupId'=>56A, 'isParent'=>1.. },
]

In above list, groupId signifies that the item is a part of bundle. GroupId uniquely determines the bundle group. If group Id is not present then its a non bundle item.

Aim - To re-order the list such that all the bundle items should be grouped together with parent item in the starting of every bundle and the incoming order of the bundle and non bundle items (when groupId not present) should remain unchanged. To sort the list in O(n)

Expected Output:

    [
     {id=> 'id1', ..},
     {id=> 'id4', 'groupId'=>45D, 'isParent'=>1 .. },
     {id=> 'id2', 'groupId'=>45D,.. },
     {id=> 'id6', 'groupId'=>56A, 'isParent'=>1.. },
     {id=> 'id3', 'groupId'=>56A, .. },
     {id=> 'id5', ..},
    ]

Here my Algo:

Create a sortedList of Ids = @sortedLineitemsIds
Use sortedIdsList to form the final sorted list

Code for #1

        my $grouIdToLineItemIdMap;

        foreach my $lineItem (@$lineItems) {
            if(!$lineItem->{'groupID'}) { #non bundle item, add as it is
                push @sortedLineitemsIds, $lineItem->{'id'};
            } else {
                if($lineItem->{'IsParent'} eq 1) {
                    unshift @{$grouIdToLineItemIdMap->{$groupId}}, $lineItem->{'id'};
                } else {
                    push @{$grouIdToLineItemIdMap->{$groupId}}, $lineItem->{'id'};
                }
            }
        }

        push @sortedLineitemsIds, $grouIdToLineItemIdMap; # **[[Question 1]]** This will always add bundle items at the end irrespective of whether it was in starting or end.

Now this will yield sortedLineitemsIds =>

    $VAR1 = [
     'id1',
     'id5',
     {
      '45D' => [
        'id4:',
        'id2:'
       ],
      '56A' => [
        'id6:',
        'id3:'
      ]
     }
   ];

Code for #2

    foreach my $Id (@sortedLineitemsIds) {
        if(determineIfSingleIdOrMapOfGroupId) { #**[[Question 2]]**
            my $lineItem = grep @lineItems with $Id; #**[[Question 3]]**
            push @sortedLineItems, $lineItem;
        } else {
             my $listOfLineItemsForGroupId = $sortedLineitemsIds->{$Id};
             foreach groupLineItemId (@$listOfLineItemsForGroupId) {
                 my $lineItem = grep @lineItems with groupLineItemId; #**[[Question 3]]**
                 push @sortedLineItems, $lineItem;
             }
        }
    }

I have now 3 questions marked above at different places in the code:

Question 1 -> Here I dont want to change the incoming order of items. Just group them. But what I am doing is it is pushing all the lineItems of the group in map, which I am appending at end after the loop. How can I can do that in the loop to preserve that order?
Question 2 -> How can I determine whether it is a single Id (non bundle id) or a groupID (basically a ref containing the lineItemIds)?
Question 3 -> How can I grep the orginal list based on the 'id' and get the corresponding lineItem?

user_589924 · Answer

You say you don't want to change the order of the items, but that's clearly not true. I'm going to assume you meant this:

I want to preserve the relative order of items which are either independent or the first of their group.

This can indeed be done in O(N).

We're going to build this:

my @grouped = (
    [ $lineItem_id1 ],
    [ $lineItem_id4, $lineItem_id2 ],
    [ $lineItem_id6, $lineItem_id3 ],
    [ $lineItem_id5 ],
);

To achieve that, we're going to use the following algorithm:

For each item,
1. If the item is independent,
  1. Add it to @grouped.
2. Else,
  1. Lookup if we've encountered the item's group before.
  2. If the item is part of a group we haven't encountered before,
    1. If it's the parent,
      1. Add it to start of the existing group.
    2. Else,
      1. Add it to end of the existing group.
  3. Else,
    1. Create a new group from the item.
    2. Add the new group to @grouped.
    3. Add the new group to the lookup hash.

At the end of this, we'll end up with the following:

my $group_45D = [ $lineItem_id4, $lineItem_id2 ];
my $group_56A = [ $lineItem_id6, $lineItem_id3 ];

my %groups = (
   '45D' => $group_45D,
   '56A' => $group_56A,
);

my @grouped = (
    [ $lineItem_id1 ],
    $group_45D,
    $group_56A,
    [ $lineItem_id5 ],
);

Solution:

my @grouped;
{
   my %groups;
   for my $lineItem (@$lineItems) {
      if ( my $groupId = $lineItem->{groupId} ) {
         if (!$groups{$groupId}) {
            push @grouped, $groups{$groupId} = [];
         }

         if ($lineItem->{isParent}) {
             unshift @{ $groups{$groupId} }, $lineItem;
         } else {
             push @{ $groups{$groupId} }, $lineItem;
         }
      } else {
         push @grouped, [ $lineItem ];
      }
   }
}

Finally, we simply need to flatten the list.

my @ordered = map { @$_ } @grouped;

Tested.

Customized Reordering/Sorting of a List in Perl in O(n)

1 Answers