Re-arrange unsorted array such that it follows specified pattern-CodePudding

Given an array of names such as:

let names = [Jewel, Crown, Rob, Rob, Jewel, Crown]

How can I re-arrange the array so that it would be in the following order:

[Jewel, Crown, Rob, Jewel, Crown, Rob]

Basically this function should accept an unsorted array of names and re-arrange it such that it returns an array following the same order in the example above. I was thinking of using the .filter method in javascript but I'm having trouble figuring out how I would implement something like this. Any help would be greatly appreciated!

CodePudding user response：

I made this function. In addition it adds to the end of the list the elements that are not part of the sorting pattern.

let names = ["Jewel", "Crown", "Rob", "Rob", "Jewel", "Crown"];
let namesWithUnknown = ["Jewel", "Crown", "Rob", "Rob", "Jewel", "Test unknown name", "Crown"];

function sortNames(unsortedNames) {
    const unsortedNamesCopy = [...unsortedNames]
    const res = [];
    const nextNames = {"Jewel": "Crown", "Crown": "Rob", "Rob": "Jewel"};
    let nextName = "Jewel";
    let count = 0;

    while (unsortedNamesCopy.length !== 0 && count < 3) {
        count  ;
        if (unsortedNamesCopy.includes(nextName)) {
            res.push(nextName);
            unsortedNamesCopy.splice(unsortedNamesCopy.findIndex(name => name === nextName), 1);
            count = 1;
        }
        nextName = nextNames[nextName];
    }

    return res.concat(unsortedNamesCopy);
}

console.log(sortNames(names));
console.log(sortNames(namesWithUnknown));

CodePudding user response：

Your requirements are still quite unclear. Here's one attempt that makes the following assumptions:

The pattern is to repeat one of each name in the same order... at least until we run out of instances of a given name, then repeat one of each of the remaining ones, etc. Thus ['Jewel', 'Crown', 'Rob', 'Rob', 'Rob', 'Jewel', 'Rob', 'Crown', 'Jewel', 'Rob'] could become ['Rob', 'Jewel', 'Crown', 'Rob', 'Jewel', 'Crown', 'Rob', 'Jewel', 'Rob', 'Rob'], where we include ['Rob', 'Jewel', 'Crown'] twice, then run out of 'Crown``s, then include ['Rob', 'Jewel'] once, then run our of 'Jewel's, and include the (one) remaining 'Rob'. Perhaps you know that your input is balanced and you don't have to worry about this scenario, but it doesn't hurt much.
The initial order does not matter at all. Instead of ['Jewel', 'Crown', 'Rob', 'Jewel', 'Crown', 'Rob'] this would be equally valid: `['Rob', 'Crown', 'Jewel', 'Rob', 'Crown', 'Jewel'].
Your values are strings or something else that can serve as object keys.

The implementation looks like this:

const counts = (names) => 
  Object .entries (names .reduce ((a, n) => ((a [n] = (a [n] || 0)   1), a), {}))

const reorder = (cs, counts = cs .filter (([_, c]) => c > 0) .sort (([, a], [, b]) => b - a)) => counts .length
  ? [...counts .map (([n]) => n), ...reorder (counts .map (([n, c]) => [n, c - 1])) ] 
  : []

const rearrange = (names) => reorder (counts (names))

console .log (rearrange (["Jewel", "Crown", "Rob", "Rob", "Jewel", "Crown"]))
console .log (rearrange (["Jewel", "Crown", "Rob", "Rob", "Rob", "Jewel", "Rob", "Crown"]))
console .log (rearrange (["John", "Larry", "Randy", "Randy", "John", "Larry"]))

.as-console-wrapper {max-height: 100% !important; top: 0}

We have two helper functions. The first, count turns your array into an array of pairs, containing the value and the count of the value in the original array, sorted descending by the counts. For instance:

counts (['Rob', 'Jewel', 'Crown', 'Rob', 'Jewel', 'Crown', 'Rob', 'Jewel', 'Rob', 'Rob])
  //=> `[['Rob', 5], ['Jewel', 3], ['Crown', 2]]`

The second one, reorder does the real work, extracting one of each of the elements that still have a count, reducing all the counts by one, and recurring, stopping with an empty array when there are no more non-empty sets.

The main function rearrange just composes those two functions.