Группировка чисел на основе вхождений?

Ответ 1

Как уже упоминалось о клике. Если вам нужен точный ответ, вы столкнетесь с проблемой максимальной клики, которая будет NP-полной. Итак, все ниже имеет смысл, только если алфавит ваших символов (цифр) имеет разумный размер. В этом случае прорывный, не очень оптимизированный алгоритм для максимальной проблемы клики в псевдокоде будет

Function Main
    Cm ← ∅                   // the maximum clique
    Clique(∅,V)              // V vertices set
    return Cm
End function Main

Function Clique(set C, set P) // C the current clique, P candidat set
    if (|C| > |Cm|) then
        Cm ← C
    End if
    if (|C|+|P|>|Cm|)then
        for all p ∈ P in predetermined order, do
            P ← P \ {p}
            Cp ←C ∪ {p}
            Pp ←P ∩ N(p)        //N(p) set of the vertices adjacent to p
            Clique(Cp,Pp)
        End for
    End if
End function Clique

Из-за Go мой язык выбора - это реализация

package main

import (
    "bufio"
    "fmt"
    "sort"
    "strconv"
    "strings"
)

var adjmatrix map[int]map[int]int = make(map[int]map[int]int)
var Cm []int = make([]int, 0)
var frequency int


//For filter
type resoult [][]int
var res resoult
var filter map[int]bool = make(map[int]bool)
var bf int
//For filter


//That for sorting
func (r resoult) Less(i, j int) bool {
    return len(r[i]) > len(r[j])
}

func (r resoult) Swap(i, j int) {
    r[i], r[j] = r[j], r[i]
}

func (r resoult) Len() int {
    return len(r)
}
//That for sorting


//Work done here
func Clique(C []int, P map[int]bool) {
    if len(C) >= len(Cm) {

        Cm = make([]int, len(C))
        copy(Cm, C)
    }
    if len(C)+len(P) >= len(Cm) {
        for k, _ := range P {
            delete(P, k)
            Cp := make([]int, len(C)+1)
            copy(Cp, append(C, k))
            Pp := make(map[int]bool)
            for n, m := range adjmatrix[k] {
                _, ok := P[n]
                if ok && m >= frequency {
                    Pp[n] = true
                }
            }
            Clique(Cp, Pp)

            res = append(res, Cp)
            //Cleanup resoult
            bf := 0
            for _, v := range Cp {
                bf += 1 << uint(v)
            }
            _, ok := filter[bf]
            if !ok {
                filter[bf] = true
                res = append(res, Cp)
            }
            //Cleanup resoult
        }
    }
}
//Work done here

func main() {
    var toks []string
    var numbers []int
    var number int


//Input parsing
    StrReader := strings.NewReader(`1,2,3
4,3,5
4,1,6
4,2,7
4,1,7
2,1,3
5,1,2
3,6`)
    scanner := bufio.NewScanner(StrReader)
    for scanner.Scan() {
        toks = strings.Split(scanner.Text(), ",")
        numbers = []int{}
        for _, v := range toks {
            number, _ = strconv.Atoi(v)
            numbers = append(numbers, number)

        }
        for k, v := range numbers {
            for _, m := range numbers[k:] {
                _, ok := adjmatrix[v]
                if !ok {
                    adjmatrix[v] = make(map[int]int)
                }
                _, ok = adjmatrix[m]
                if !ok {
                    adjmatrix[m] = make(map[int]int)
                }
                if m != v {
                    adjmatrix[v][m]++
                    adjmatrix[m][v]++
                    if adjmatrix[v][m] > frequency {
                        frequency = adjmatrix[v][m]
                    }
                }

            }
        }
    }
    //Input parsing

    P1 := make(map[int]bool)


    //Iterating for frequency of appearance in group
    for ; frequency > 0; frequency-- {
        for k, _ := range adjmatrix {
            P1[k] = true
        }
        Cm = make([]int, 0)
        res = make(resoult, 0)
        Clique(make([]int, 0), P1)
        sort.Sort(res)
        fmt.Print(frequency, "x-times ", res, " ")
    }
    //Iterating for frequency of appearing together
}

И здесь вы можете увидеть, как он работает https://play.golang.org/p/ZiJfH4Q6GJ и воспроизводит входные данные. Но еще раз этот подход подходит для разумного размера алфавита (и входных данных любого размера).

Ответ 2

Каждая из трех последовательностей может быть понята как clique в multigraph. Внутри клики каждая вершина связана с каждой другой вершиной.

Следующий график представляет ваш пример с краями в каждой клике, цветной красный, синий и зеленый соответственно.

Как вы уже показали, мы можем классифицировать пары вершин в соответствии с количеством ребер между ними. На иллюстрации мы видим, что четыре пары вершин связаны двумя ребрами, а четыре другие пары вершин связаны одним ребром.

Мы можем продолжить классификацию вершин в соответствии с количеством кликов, в которых они отображаются. В некотором смысле мы ранжируем вершины в соответствии с их связностью. Вершина, которая появляется в кликах k, может рассматриваться как связанная с той же степенью, что и другие вершины, которые появляются в k cliques. На изображении мы видим три группы вершин: вершина 3 появляется в трех кликах; вершины 1, 2 и 4 кажутся в двух кликах; вершина 5 появляется в одной клике.

В приведенной ниже программе Go вычисляется классификация ребер, а также классификация вершин. Ввод в программу содержит в первой строке число вершин n и количество клик m. Предположим, что вершины нумеруются от 1 до n. Каждая из последующих строк ввода m представляет собой список вершин, принадлежащих клике, разделенных пробелами. Таким образом, экземпляр проблемы, заданный в вопросе, представлен этим вводом:

5 3
1 2 3 4
4 3 5
2 1 3

Соответствующий выход:

Number of edges between pairs of vertices:
    2 edges: (1, 2) (1, 3) (2, 3) (3, 4)
    1 edge:  (1, 4) (2, 4) (3, 5) (4, 5)

Number of cliques in which a vertex appears:
    3 cliques: 3
    2 cliques: 1 2 4
    1 clique:  5

И вот программа Go:

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

func main() {
        // Set up input and output.
        reader := bufio.NewReader(os.Stdin)
        writer := bufio.NewWriter(os.Stdout)
        defer writer.Flush()

        // Get the number of vertices and number of cliques from the first line.
        line, err := reader.ReadString('\n')
        if err != nil {
                fmt.Fprintf(os.Stderr, "Error reading first line: %s\n", err)
                return
        }
        var numVertices, numCliques int
        numScanned, err := fmt.Sscanf(line, "%d %d", &numVertices, &numCliques)
        if numScanned != 2 || err != nil {
                fmt.Fprintf(os.Stderr, "Error parsing input parameters: %s\n", err)   
                return
        }

        // Initialize the edge counts and vertex counts.
        edgeCounts := make([][]int, numVertices+1)
        for u := 1; u <= numVertices; u++ {
                edgeCounts[u] = make([]int, numVertices+1)
        }
        vertexCounts := make([]int, numVertices+1)

        // Read each clique and update the edge counts.
        for c := 0; c < numCliques; c++ {
                line, err = reader.ReadString('\n')
                if err != nil {
                        fmt.Fprintf(os.Stderr, "Error reading clique: %s\n", err)
                        return
                }
                tokens := strings.Split(strings.TrimSpace(line), " ")
                clique := make([]int, len(tokens))
                for i, token := range tokens {
                        u, err := strconv.Atoi(token)
                        if err != nil {
                                fmt.Fprintf(os.Stderr, "Atoi error: %s\n", err)
                                return
                        }
                        vertexCounts[u]++
                        clique[i] = u
                        for j := 0; j < i; j++ {
                                v := clique[j]
                                edgeCounts[u][v]++
                                edgeCounts[v][u]++
                        }
                }
        }

        // Compute the number of edges between each pair of vertices.
        count2edges := make([][][]int, numCliques+1)
        for u := 1; u < numVertices; u++ {
                for v := u + 1; v <= numVertices; v++ {
                        count := edgeCounts[u][v]
                        count2edges[count] = append(count2edges[count],
                                []int{u, v})
                }
        }
        writer.WriteString("Number of edges between pairs of vertices:\n")
        for count := numCliques; count >= 1; count-- {
                edges := count2edges[count]
                if len(edges) == 0 {
                        continue
                }
                label := "edge"
                if count > 1 {
                        label += "s:"
                } else {
                        label += ": "
                }
                writer.WriteString(fmt.Sprintf("%5d %s", count, label))
                for _, edge := range edges {
                        writer.WriteString(fmt.Sprintf(" (%d, %d)",
                                edge[0], edge[1]))
                }
                writer.WriteString("\n")
        }

        // Group vertices according to the number of clique memberships.
        count2vertices := make([][]int, numCliques+1)
        for u := 1; u <= numVertices; u++ {
                count := vertexCounts[u]
                count2vertices[count] = append(count2vertices[count], u)
        }
        writer.WriteString("\nNumber of cliques in which a vertex appears:\n")
        for count := numCliques; count >= 1; count-- {
                vertices := count2vertices[count]
                if len(vertices) == 0 {
                        continue
                }
                label := "clique"
                if count > 1 {
                        label += "s:"
                } else {
                        label += ": "
                }
                writer.WriteString(fmt.Sprintf("%5d %s", count, label))
                for _, u := range vertices {
                        writer.WriteString(fmt.Sprintf(" %d", u))
                }
                writer.WriteString("\n")
        }
}

Ответ 3

Эта проблема часто возникает в контексте разработки правил при анализе данных о продажах. (Какие предметы покупаются вместе, поэтому их можно разместить рядом друг с другом в супермаркете)

Один класс алгоритмов, с которыми я столкнулся, - Обучение правилам ассоциации. И один неотъемлемый шаг - поиск частых наборов предметов, который соответствует вашей задаче. Один алгоритм Apriori. Но при поиске этих ключевых слов вы можете найти гораздо больше.

Ответ 4

Было бы лучше, если бы вы описали цель такой группировки. Если нет, я могу попытаться предложить простые (как мне кажется) подход, и он будет наиболее ограниченным. Это не подходит, если вам нужно подсчитать огромное количество широко распространенных (например, 1, 999999, 31) или больших или неположительных чисел. вы можете упорядочить наборы чисел в таких позициях массива:

  |1|2|3|4|5|6|  - numers as array positions
==============
*1|1|1|1|1|0|0| *1     
*2|0|0|1|1|1|0| *2   
*4|1|1|1|0|0|0| *4
==============
 +|2|2|3|2|1|0  - just a counters of occurence
 *|5|5|7|3|2|0  - so for first column number 1 mask will be: 1*1+1*4 = 5 

здесь вы можете видеть в + строке, что наиболее часто встречающейся комбинацией является [3], затем [1,2] и [4], а затем [5], также вы можете указать и отличить кокурятельность различных комбинаций

    function grps(a) {
      var r = [];
      var sum = []; var mask = [];
      var max = 0;
      var val;
      for (i=0; i < a.length; i++) {
        for (j=0; j < a[i].length; j++) {
          val = a[i][j]; 
          //r[i][val] = 1;
          sum[val] = sum[val]?sum[val]+1:1; 
          mask[val] = mask[val]?mask[val]+Math.pow(2, i):1;
          if (val > max) { max = val; }
        }
      }
      for (j = 0; j < max; j++){
        for (i = 0; i < max; i++){            
          r[sum[j]][mask[j]] = j;
        }
      }
      return r;
    }