查找通常在数组中彼此相邻的元素 [英] Find elements that commonly appear next to each other in an array

问题描述

我试图找到通常在数组中彼此相邻的值。

E.G。给定数组：

  [dog，cat，goat，dog，cat，大象，狗，猫，猪，海豹，狗，猫，猪，猴子] 
  

它应该返回类似于：

  [[[dog ，cat]，4]，[[cat，pig]，2]，[[dog，cat，pig]，2]] 
  

以下是一些更好的数据： https ：//pastebin.com/UG4iswrZ

非常感谢帮助。以下是我目前尝试做类似事情的失败：

  function findAssociations（words）{
 var temp = [] ，tempStore = []，store = []，found = false; 
 //循环计算单词的出现次数以及5 
的窗口（var i = 0; i< words.length-1; i ++）{
 if（i％） 5 == 0）{
 //在每个fith元素上，循环通过商店尝试添加存储在tempStore 
中的单词组合（var j = 0; j <5; j ++）{
 temp = [] 
 //为（var k = 0; k< j; k ++）{
 temp.push（tempStore [k]）创建当前组合
; 
} 
 //查找元素是否已经存储，如果是，则将出现计数器
递增为（var k = 0; k< store.length; k ++）{
 if（store [k] [0] === temp）{
 found = true; 
 store [k] [1] = store [k] [1] +1; 
} 
} 
 //如果不添加
 if（found == false）{
 store.push（[temp，1]）; 
} 
 found == false; 
} 
 tempStore = []; 
} else {
 //如果我不是5 
 tempStore.push（words [i]）的倍数，则向tempStore添加单词; 
} 
} 
} 
  

这个脚本不是删除出现一次的组合，它不会按出现次数对输出进行排序，也不会起作用。这只是一个可能的解决方案如何工作的概述（正如benvc所建议的那样）。

解决方案

这是一个使用多个组大小的通用解决方案。

您指定了一系列组大小，例如 [2,4] 适用于2到4个元素的组和最小出现次数。

该函数然后生成给定大小的所有邻居组，对每个组进行排序并计算重复数。排序步骤可以删除组中的顺序事项。

通过创建一个字典来计算重复项，该字典的键是使用特殊标记排序和连接的组元素。字典中的值是计数。

然后返回按出现次数排序的组，然后按组大小排序。

< pre class =snippet-code-js lang-js prettyprint-override> const data = [dog，cat，goat，dog，cat，elephant ，dog，cat，pig，seal，dog，cat，pig，monkey]; function findSimilarNeighbors（groupSizeRange，minOccurences，data）{const getNeighbors =（size， arr）=> arr.reduce（（acc，x）=> {acc.push（[]）; for（let i = 0; i< size; ++ i）{const idx = acc.length - i - 1;（ acc [idx] || []）。push（x）;} return acc;}，[]）。filter（x => x.length === size）; const groups = []; for（let groupSize = groupSizeRange [0]; groupSize< = groupSizeRange [1]; ++ groupSize）{groups.push（... getNeighbors（groupSize，data））; } const groupName = group => 。group.sort（）加入（ @＃@）; //使用不会出现在字符串中的分隔符const groupsInfo = groups.reduce（（acc，group）=> {const name = groupName（group）; acc [name] = acc [name] || {} ; acc [name] = {group，count：（acc [name] .count || 0）+ 1}; return acc;}，{}）; return Object.values（groupsInfo）.filter（group => group.count> = minOccurences）.sort（（a，b）=> {const countDiff = b.count - a.count; return countDiff？countDiff： b.group.length - a.group.length;}）。map（（{group，count}）=> [group，count]）;}; console.log（findSimilarNeighbors（[2,4]，2， data））; console.log（findSimilarNeighbors（[4,4]，2，data））;

I am trying to find values that commonly appear next to each other in an array.

E.G. given the array:

["dog","cat","goat","dog","cat","elephant","dog","cat","pig","seal","dog","cat","pig","monkey"]

it should return something similar to:

[[["dog","cat"],4],[["cat","pig"],2],[["dog","cat","pig"],2]]

Here is some better data: https://pastebin.com/UG4iswrZ

Help would be greatly appreciated. Here is my current failed attempt at doing something similar:

function findAssociations(words){
  var temp = [],tempStore = [],store = [],found = false;
  //loop through the words counting occurrances of words together with a window of 5
  for(var i = 0;i<words.length-1;i++){
    if(i % 5 == 0){
      //on every fith element, loop through store attempting to add combinations of words stored in tempStore
      for(var j = 0;j<5;j++){
        temp = []
        //create the current combination
        for(var k = 0;k<j;k++){
          temp.push(tempStore[k]);
        }
        //find if element is already stored, if it is, increment the occurrence counter
        for(var k = 0;k<store.length;k++){
          if(store[k][0]===temp){
            found = true;
            store[k][1] = store[k][1]+1;
          }
        }
        //if it isn't add it
        if(found == false){
          store.push([temp,1]);
        }
        found == false;
      }
      tempStore = [];
    } else {
      //add word to tempStore if it i isnt a multiple of 5
      tempStore.push(words[i]);
    }
  }
}

This script is doesn't remove combinations that appear once,it doesn't sort the output by occurrences, nor does it work. It is just an outline of how a possible solution might work (as suggested by benvc).

解决方案

Here is a generic solution working with multiple group sizes.

You specify a range of group sizes, for example [2,4] for groups of 2 to 4 elements and a minimum number of occurrences.

The function then generates all groups of neighbours of the given sizes, sorts each group and counts the duplicates. The sorting step can be removed is the order in the groups matters.

The duplicates are counted by creating a dictionary whose keys are the group elements sorted and jointed with a special marker. The values in the dictionary are the counts.

It then returns the groups sorted by occurences and then by group size.

const data = ["dog","cat","goat","dog","cat","elephant","dog","cat","pig","seal","dog","cat","pig","monkey"];

function findSimilarNeighbors(groupSizeRange, minOccurences, data) {
  const getNeighbors = (size, arr) => arr.reduce((acc, x) => {
    acc.push([]);
    for (let i = 0; i < size; ++ i) {
      const idx = acc.length - i - 1;
      (acc[idx] || []).push(x);
    }
    return acc;
  }, []).filter(x => x.length === size);

  const groups = [];
  for (let groupSize = groupSizeRange[0]; groupSize <= groupSizeRange[1]; ++groupSize) {
    groups.push(...getNeighbors(groupSize, data));
  }
  const groupName = group => group.sort().join('@#@'); // use a separator that won't occur in the strings

  const groupsInfo = groups.reduce((acc, group) => {
    const name = groupName(group);
    acc[name] = acc[name] || {};
    acc[name] = { group, count: (acc[name].count || 0) + 1 };
    return acc;
  }, {});
  
  return Object.values(groupsInfo)
    .filter(group => group.count >= minOccurences)
    .sort((a, b) => {
      const countDiff = b.count - a.count;
      return countDiff ? countDiff : b.group.length - a.group.length;
    })
    .map(({ group, count }) => [group, count]);
};

console.log(findSimilarNeighbors([2, 4], 2, data));
console.log(findSimilarNeighbors([4, 4], 2, data));

这篇关于查找通常在数组中彼此相邻的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！