解决递归方法

Question

我有三个变量

一组人 例如：{{David, Sebastian, Yousef}, {Boris, Mark}}

人物集 例如：{David、Mark、Sebastian、Boris、Yousef}

关系集 例如：{{David, Mark}, {Sebastian, Boris}}

一个Group-Set不能有任何人是彼此的朋友。

组集不能有重复项。

我需要创建一个名为

的除法

划分(person-set, relation-set)和returns一个group-set如上例

需要递归求解，不允许循环

我已经有一个名为 areFriends(Person, Person) 的方法，returns 如果他们是朋友，它是一个布尔值。

这是我目前得到的：

divide(ps, r){
    divide(ps, r, gs){

    let p1 = getRandom(ps);
        p2 = getRandom(ps);

    if(areFriends(p1, p2) = false){
      gs.add(p1);
      gs.add(p2);
    }


    remove(p1, ps);
    if(getRandom(ps) != 0){
    divide(ps, r, gs);
  }
}

我已经处理这个问题很长时间了，真的需要帮助。谢谢！

Answer 1

基于一个新的约束（没有循环约束），我们需要一个指标（g_ind）来考虑函数中的组：

divide(ps, r, g = [[]], g_ind = 0)

    p <- empty
    if there is any person in ps:
        p <- take the first person from ps
    else:
        return
    
    if g_ind >= len(g):
        // all current divisions in g have a friend of p
       g.add([p]) // add a new division with initial member p
       remove p from ps
       divide(ps, r, g, 0)
       return  
    else if any friends of p in r exists in g[g_ind]:
       divide(ps, r, g, ++g_ind)
       return
    else:
        g[g_ind].add(p)
        remove p from ps
        divide(ps, r, g, 0)
        return

解决递归方法

Solving a recursive method

algorithm

recursion

pseudocode