The name of the algorithm that describes the group sequence
I have an array of arrays, for example:
var groups = [
['one', 'three', 'four'],
['two', 'three', 'six', 'seven'],
['three', 'four', 'five'],
]
From this, I need to deduce the appropriate sequence of values based on the order they are given (I gave numbers for an easy example). In other words, since there is no data in each array, other arrays must be referenced to get the optimal sequence of all groups. Ideal way out:
['one', 'two', 'three', 'four', 'five', 'six', 'seven'];
I can write this, but I'm pretty sure it's a fairly common algorithm. I just don't know his name. Any ideas (or an easy way to solve them)?
source to share
One possible approach is to use topological sort to find the shortest path in a directed acyclic graph:
- Define a node for each unique word "
- Define a directed edge between adjacent "words" in a group going from left (original) to right (sink)
- Calculate the weight of each edge as some function measuring the number of times two words are in two groups of each other (you need to experiment here).
- Compute the set of topological orders of the constructed DAG.
- Calculate shortest path in DAG.
The resulting path is your decision. Note that you will need to make sure your groups define an acyclic graph.
source to share
Let me write in php. I am trying to comment out all lines
$groups = [
['one', 'three', 'four'],
['two', 'three', 'six', 'seven'],
['three', 'four', 'five'],
];
$maxl = 0; // max length of nested arrays
foreach($groups as $item) // walk through array
if ((count($item) > $maxl)) // if current array is longer
$maxl = count($item); // save it length
$result = []; // will be result
for ($i = 0; $i < $maxl; $i++) // vertical slice of the array
for ($j = 0; $j < count($groups); $j++) // loop through nested arrays
if(isset($groups[$j][$i]) && // if such element is present
!in_array($groups[$j][$i], $result)) // and not in result yet
$result[] = $groups[$j][$i]; // add it
print_r($result);
But I can't figure out the order of five and six, so the result is:
Array
(
[0] => one
[1] => two
[2] => three
[3] => four
[4] => six
[5] => five
[6] => seven
)
source to share
How it works
path = [
[ "one", "three" ],
[ "three", "four" ],
[ "two", "three" ],
[ "three", "six" ],
[ "six", "seven" ],
[ "three", "four" ],
[ "four", "five" ]
]
Operation Result
------------------------------------ ----------------------------------
0 push(one) one
1 splice(1, 0, three) one,three
0 push(three) one,three,three
0 splice(2, 1) delete last double one,three
1 splice(2, 0, four) one,three,four
0 splice(1, 0, two) one,two,three,four
1 splice(2, 0, three) one,two,three,three,four
1 splice(3, 1) delete last double one,two,three,four
0 push(three) one,two,three,four,three
0 splice(4, 1) delete last double one,two,three,four
1 splice(3, 0, six) one,two,three,six,four
0 push(six) one,two,three,six,four,six
0 splice(5, 1) delete last double one,two,three,six,four
1 splice(4, 0, seven) one,two,three,six,seven,four
0 splice(5, 0, three) one,two,three,six,seven,three,four
0 splice(5, 1) delete last double one,two,three,six,seven,four
1 splice(3, 0, four) one,two,three,four,six,seven,four
1 splice(6, 1) delete last double one,two,three,four,six,seven
0 push(four) one,two,three,four,six,seven,four
0 splice(6, 1) delete last double one,two,three,four,six,seven
1 splice(4, 0, five) one,two,three,four,five,six,seven
Basically it gets the path from all combined elements in the array with start / target pairs. The path then goes down, and for each launch and target, a search for a predecessor or successor is looked through. If a predecessor is found, then the item is inserted into the index and if the successor is after the index. If not found, the element will be placed at the end of the array.
Because each path and path target is inserted, the result is longer (2x) than required. This way the last duplicate items are removed.
var groups = [
['one', 'three', 'four'],
['two', 'three', 'six', 'seven'],
['three', 'four', 'five'],
];
function combination(a, r) {
r = r || [];
a.reduce(function (res, el) {
el.forEach(function (item, i) {
i && res.push([el[i - 1], item]);
});
return res;
}, []).forEach(function (el) {
function lookup(n, m, offset) {
var index = r.indexOf(n);
~index ? r.splice(index + offset, 0, m) : r.push(m);
r.indexOf(m) !== r.lastIndexOf(m) && r.splice(r.lastIndexOf(m), 1);
}
lookup(el[1], el[0], 0);
lookup(el[0], el[1], 1);
});
return r;
}
console.log(combination(groups));
.as-console-wrapper { max-height: 100% !important; top: 0; }
source to share
What you need is a topological sort , but be careful to have multiple solutions.
In the example you provide, your relationship only gives the following constraints:
- 1 and 2 to 3
- 4 to 5
- 6 to 7
- 4, 5, 6 and 7 after 3
This means that the correct solutions are:
- 2 1 3 4 6 7 5
- 1 2 3 6 7 4 5
- 2 1 3 6 4 7 5
Calculating the total number of topological sorts in the example provided is left as an exercise for the reader.
source to share