Множества и подмножества в PARI

[gris]

Для множества натуральных чисел от $1$ до $n$ задано семейство $m\leq n$ подмножеств. Требуется в каждом подмножестве выбрать по одному элементу отличному от других выбранных. При удаче — выдать вектор. Хотя бы один.
Пример:
n=5; m=5;
[1,3]
[1,3,4]
[2,5]
[2,3,4]
[4]
--------------------------
[1,3,5,2,4]; [3,1,5,2,4].
при малых числах задача решается на бумажке, но предполагаются большие числа и решение на PARI. Нет ли каких советов?

[wrest]

gris
В каком виде на вход подаются подмножества?

Ну то есть, вам нужна функция, на входе у которой то-то а на выходе - то-то.
Что на входе?

[venco]

Это в чистом виде maximal bipartite matching problem.

https://en.wikipedia.org/wiki/Hopcroft% ... _algorithm

Как это привязать к PARI - не знаю.

[wrest]

wrest в сообщении #1719757 писал(а):

Ну то есть, вам нужна функция, на входе у которой то-то а на выходе - то-то.

Хорошо, будем считать, что на вход подаётся вектор из подмножеств. Например такой:
[[1, 3], [1, 3, 4], [2, 5], [2, 3, 4], [4]]
Корректность ввода оставляем за бортом функции. Например что подмножества являются множествами т.е. элементы в подмножествах не повторяются, а также что элементы всех подмножеств принадлежат множеству [1..n] и т.п.
Вот функция, которая находит вектор из элементов, удовлетворяющий условию:

Используется синтаксис C++

{
find_selection(sets) = 
my(m, n, i, j, elem, setNum, count, pair, match, adj, found, aug, result, selection, pair_set, pair_elem, seen_set, seen_elem, queue, front, back, prev, u, v, e, s, start_set);

m = #sets;
n = 0;
for(i = 1, m,
    for(j = 1, #sets[i],
        if(sets[i][j] > n, n = sets[i][j])
    )
);

adj = vector(m);
for(i = 1, m, adj[i] = sets[i]);

match = vector(m, i, 0);  \\ match[set] = элемент
pair = vector(n, j, 0);   \\ pair[elem] = множество

for(start_set = 1, m,
    if(match[start_set] == 0,
        seen_set = vector(m, i, 0);
        seen_elem = vector(n, j, 0);
        prev = vector(m + n, i, 0);
        queue = vector(m + n);
        front = 1; back = 1;
        
        queue[back] = start_set;
        back = back + 1;
        seen_set[start_set] = 1;
        prev[start_set] = -1;
        
        found = 0;
        aug = 0;
        
        while(front < back && !found,
            v = queue[front];
            front = front + 1;
            
            if(v <= m, \\ Это множество
                for(k = 1, #adj[v],
                    e = adj[v][k];
                    if(e <= n && !seen_elem[e],
                        seen_elem[e] = 1;
                        queue[back] = m + e;
                        back = back + 1;
                        prev[m + e] = v;
                        
                        if(pair[e] == 0,
                            found = 1;
                            aug = m + e;
                            break;
                        );
                    );
                );
            , \\ Это элемент (v > m)
                e = v - m;
                s = pair[e];
                if(s != 0 && !seen_set[s],
                    seen_set[s] = 1;
                    queue[back] = s;
                    back = back + 1;
                    prev[s] = v;
                );
            );
            if(found, break);
        );
        
        if(found,
            u = aug;
            while(1,
                v = prev[u];
                if(v < 0, break);
                if(u > m,
                    e = u - m;
                    s = v;
                    if(s <= m && e <= n && setsearch(Set(adj[s]), e),
                        match[s] = e;
                        pair[e] = s;
                    );
                );
                u = v;
            );
        );
    );
);

count = 0;
selection = vector(m, i, 0);
for(i = 1, m,
    if(match[i] > 0,
        if(setsearch(Set(sets[i]), match[i]),
            selection[i] = match[i];
            count++;
        );
    )
);

if(count == m,
    print("Можно выбрать. Один из вариантов:");
    for(i = 1, m,
        print("Множество ", i, " (", sets[i], ") -> элемент ", selection[i]);
    );
    return(selection);
,
    print("Невозможно выбрать по одному различному элементу из каждого множества");
    return(0);
);
}

Запускаем:

? find_selection([[1,3],[1,3,4],[2,5],[2,3,4],[4]])
Можно выбрать. Один из вариантов:
Множество 1 ([1, 3]) -> элемент 1
Множество 2 ([1, 3, 4]) -> элемент 3
Множество 3 ([2, 5]) -> элемент 5
Множество 4 ([2, 3, 4]) -> элемент 2
Множество 5 ([4]) -> элемент 4
cpu time = 1 ms, real time = 2 ms.
%6 = [1, 3, 5, 2, 4]

Спасибо отправляем в DeepSeek

P.S. Вот другая версия этой функции

Используется синтаксис C++

find_selection(sets, flag = 0) = {
my(m, n, i, j, elem, setNum, count, pair, match, adj, found, aug, result, selection, pair_set, pair_elem, seen_set, seen_elem, queue, front, back, prev, u, v, e, s, start_set, all_solutions, solutions, temp, used_elem, used_set, current, level, k, stack, indices, valid, solution_count);

m = #sets;
n = 0;
for(i = 1, m,
    for(j = 1, #sets[i],
        if(sets[i][j] > n, n = sets[i][j])
    )
);

adj = vector(m);
for(i = 1, m, adj[i] = sets[i]);

if(flag == 0,
    match = vector(m, i, 0);
    pair = vector(n, j, 0);
    
    for(start_set = 1, m,
        if(match[start_set] == 0,
            seen_set = vector(m, i, 0);
            seen_elem = vector(n, j, 0);
            prev = vector(m + n, i, 0);
            queue = vector(m + n);
            front = 1; back = 1;
            
            queue[back] = start_set;
            back = back + 1;
            seen_set[start_set] = 1;
            prev[start_set] = -1;
            
            found = 0;
            aug = 0;
            
            while(front < back && !found,
                v = queue[front];
                front = front + 1;
                
                if(v <= m,
                    for(k = 1, #adj[v],
                        e = adj[v][k];
                        if(e <= n && !seen_elem[e],
                            seen_elem[e] = 1;
                            queue[back] = m + e;
                            back = back + 1;
                            prev[m + e] = v;
                            
                            if(pair[e] == 0,
                                found = 1;
                                aug = m + e;
                                break;
                            );
                        );
                    );
                ,
                    e = v - m;
                    s = pair[e];
                    if(s != 0 && !seen_set[s],
                        seen_set[s] = 1;
                        queue[back] = s;
                        back = back + 1;
                        prev[s] = v;
                    );
                );
                if(found, break);
            );
            
            if(found,
                u = aug;
                while(1,
                    v = prev[u];
                    if(v < 0, break);
                    if(u > m,
                        e = u - m;
                        s = v;
                        if(s <= m && e <= n && setsearch(Set(adj[s]), e),
                            match[s] = e;
                            pair[e] = s;
                        );
                    );
                    u = v;
                );
            );
        );
    );
    
    count = 0;
    selection = vector(m, i, 0);
    for(i = 1, m,
        if(match[i] > 0 && setsearch(Set(sets[i]), match[i]),
            selection[i] = match[i];
            count++;
        )
    );
    
    if(count == m,
        return(selection);
    ,
        return(0);
    );
,
    solutions = [];
    used_elem = vector(n, j, 0);
    current = vector(m, i, 0);
    level = 1;
    
    stack = [[1, 0]];
    
    while(#stack > 0,
        level = stack[#stack][1];
        i = stack[#stack][2] + 1;
        
        if(level > m,
            solutions = concat(solutions, [vector(m, j, current[j])]);
            stack = stack[1..#stack-1];
            next;
        );
        
        if(i > #adj[level],
            if(current[level] != 0,
                used_elem[current[level]] = 0;
                current[level] = 0;
            );
            stack = stack[1..#stack-1];
            next;
        );
        
        elem = adj[level][i];
        
        if(!used_elem[elem],
            if(current[level] != 0,
                used_elem[current[level]] = 0;
            );
            used_elem[elem] = 1;
            current[level] = elem;
            
            stack[#stack] = [level, i];
            stack = concat(stack, [[level + 1, 0]]);
        ,
            stack[#stack] = [level, i];
        );
    );
    
    return(solutions);
);
}

Она ничего не печатает только возвращает результат.
Плюс, после входных данных можно задать ключ
0- по умлочанию, искать любое решение
1 -искать все решения

Запускаем:

? find_selection([[1,3],[1,3,4],[2,5],[2,3,4],[4]])
%9 = [1, 3, 5, 2, 4]
? find_selection([[1,3],[1,3,4],[2,5],[2,3,4],[4]], 1)
cpu time = 1 ms, real time = 1 ms.
%10 = [[1, 3, 5, 2, 4], [3, 1, 5, 2, 4]]
?

Для вашего примера всего решений два.

Если решений нет, будет возвращен ноль.

[wrest]

venco
DeepSeek говорит мне что использует алгоритм Куна, https://nerc.itmo.ru/wiki/index.php?title=Алгоритм_Куна_для_поиска_максимального_паросочетания&oldid=6754

Для поиска всех решений - перебор.

[gris]

спасибо, Дипочка! Теперь есть на чем думать долгие дни...
а данные задаются в файле. Каждая строка — подмножество.

[wrest]

gris в сообщении #1719769 писал(а):

а данные задаются в файле. Каждая строка — подмножество.

А как строки выглядят?

[gris]

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

 {fout = fileopen("E:/PARI/subsets.txt","w");
N=12;
m=12;
maxl=4;
vn=vector(N,i,i);
for(i=1,N,ir=random([i,N]);[vn[i],vn[ir]]=[vn[ir],vn[i]] ); print(vn);
for(i=1,m,
   vm=vector(maxl);vm[1]=vn[i];
   for(j=2,maxl, vm[j]=vn[random([1,N])]  );
   vm=Set(vm); print(vm);
   filewrite(fout,Str(vm) );
);
fileclose(fout);
}
[3, 5, 6, 11]
[2, 5, 7, 10]
[1, 2, 6, 8]
[1, 4, 7, 12]
[2, 4, 6, 8]
[8, 9, 12]
[2, 3, 6, 8]
[1, 2, 10, 11]
[1, 3, 7, 11]
[2, 8, 11]
[2, 9, 10]
[4, 7]

Именно так они и в файле с последней пустой строкой. Попробую применить вашу программу.
Предполагаемый ответ
[5, 7, 2, 1, 6, 12, 3, 10, 11, 8, 9, 4]
Буду благодарен за замечания и подсказки :(

[wrest]

gris в сообщении #1719801 писал(а):

Предполагаемый ответ

Ну у меня получилось так:

? find_selection(read_sets("sets.txt"))
time = 5 ms.
%4 = [3, 5, 1, 12, 6, 8, 2, 10, 7, 11, 9, 4]
? #find_selection(read_sets("sets.txt"),1)
time = 155 ms.
%8 = 293
?

Всего решений 293, так что все печатать не буду :)

-- 10.03.2026, 14:53 --

Функция чтения подмножеств из файла:

Используется синтаксис C++

read_sets(filename) = {
  local(file, sets, line, vec, i);
  file = readstr(filename);
  sets = List();
  for(i = 1, #file,
    line = file[i];
    if(line != "",
      vec = eval(line);
      listput(sets, vec);
    );
  );
  return(Vec(sets));
}

Тут используется List т.к. размер заранее неизвестен, а в List можно добавлять элементы.
Но в конце List преобразуется в вектор.
Запуск на вашем файле:

? read_sets("sets.txt")
time = 1 ms.
%7 = [[3, 5, 6, 11], [2, 5, 7, 10], [1, 2, 6, 8], [1, 4, 7, 12], [2, 4, 6, 8], [8, 9, 12], [2, 3, 6, 8], [1, 2, 10, 11], [1, 3, 7, 11], [2, 8, 11], [2, 9, 10], [4, 7]]
?

[Dmitriy40]

wrest в сообщении #1719810 писал(а):

Тут используется List т.к. размер заранее неизвестен, а в List можно добавлять элементы.

Размер известен - #file. Другое дело что там могут быть пустые строки, но это легко учесть:

return(select(t->t != "", vector(#file,j, eval(file[j]) ) ) );

А можно и совсем просто, одной командой без всяких строк:

return(readvec("sets.txt"));

Но так уже недопустимы левые символы в файле, только пустые строки, которые корректно пропускаются.

[wrest]

Dmitriy40 в сообщении #1719813 писал(а):

А можно и совсем просто, одной командой без всяких строк:Код:

return(readvec("sets.txt"));

Спасибо, действительно работает как надо. Неожиданно...
Если gris будет генерить файлы в pari, то левых символов и не ожидается.

-- 10.03.2026, 16:08 --

Dmitriy40 в сообщении #1719813 писал(а):

Размер известен - #file.

А, у меня в каком-то варианте был while и там было неизвестно.