Как найти пропущенный номер в списке?

Question

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

Мое решение до сих пор:

% missing_number/2 (ListToBeChecked, ListToBeCompared, MissingNum)
missing_number([], [], []) :- !.
missing_number([Head | Tail], [Head | Rest], Number) :- 
    missing_number(Tail, Rest, Number).
missing_number(_, [X | _], [X | Node]) :- 
    missing_number(_, _, Number), !.

Answer 1

Используйте between/3 для генерации всех чисел от мин до макс. Используйте memberchk/2 (или member/2), чтобы найти недостающие.

L = [1,2,4,5],
L = [M|_],
last(L, N),
between(M, N, I),
\+ memberchk(I, L).

Упражнение для читателя: заверните это в предикат.

РЕДАКТИРОВАТЬ Эффективное решение по популярному запросу:

missing([I,K|_], M) :-
    I1 is I+1,
    K1 is K-1,
    between(I1, K1, M).
missing([_|Ns], M) :-
    missing(Ns, M).

РЕДАКТИРОВАТЬ 2 : более элегантная версия вышеупомянутого, вдохновленная @chac, не обязательно очень эффективная:

missing(L,M) :- append(_, [I,J|_], L), I1 is I+1, J1 is J-1, between(I1,J1,M).

Answer 2

Парадигматический предикат append / 3 много раз может помочь в обязанностях, связанных со списками: здесь достаточно проверить последовательные элементы, которые не являются преемниками:

missing(L, M) :-
    append(_, [A,B|_], L),
    \+ succ(A, B), succ(A, M).

Завершено

Чтобы иметь возможность заполнять пробелы длиной> 1, решение заканчивается почти идентично ларсманскому:

missing(L, M) :-
    append(_, [A,B|_], L),
    succ(A, S), succ(P, B), between(S, P, M).

succ / 2 допускает более декларативный подход, но он заметно медленнее, чем арифметика.

Answer 3

не работает для несортированных списков

missing([], []).
missing([H|T], R) :- missing([H|T], H, R).
missing([], _I, []).
missing([H|T], I, [I|R]) :-
    H =\= I,
    !,
    NextI is I + 1,
    missing([H|T], NextI, R).
missing([_|T], I, R) :-
    NextI is I + 1,
    missing(T, NextI, R).

Answer 4

Пожалуйста, смотрите ниже: Реализация в JavaScript. Но алгоритм может быть преобразован. Надеюсь, это поможет! Предполагается, что список является восходящим и представляет собой арифметический ряд - n, n + 1, n + 2 ... Кроме того, список может начинаться где угодно, а не только с 0

    function getMissingNum() {
    var start = Math.floor(Math.random() * 150) / 1;
    var nElem = Math.floor(Math.random() * 20) / 1;
    var set = [];
    var rand = Math.floor(Math.random() * nElem) + start / 1;
    for (var i = start; i <= start + nElem; i++) {
        //skip one number randomly
        if (i == rand) continue;
        set.push(i);
    }

    var sum = 0;
    for (var i = 0; i < set.length; i++) {
        sum += set[i];
    }

    // SEE HERE: 
    // Total = N * (N + 1) / 2
    var max = set[set.length - 1];
    var min = set[0];// - 1;
    var actual = (((max * (max + 1)) / 2));
    var excluded = (((min * (min + 1)) / 2));
    var missing = actual - excluded - sum + start;
    if (min > start) {
        missing = missing + min;
    }
    return {
        missing: missing,
        min: min,
        max: max,
        actual: actual,
        excluded: excluded,
        rand: rand,
        start: start,
        nElem: nElem
    }
}

var results = [];
for (var i = 0; i < 100; i++) {
    var result = getMissingNum();
    if (result.rand != result.missing) {
        results.push(result);
    }
}

Answer 5

missing([], []).
missing([H|T], R) :- missing([H|T], H, R).
missing([], _I, []).
missing([H|T], I, [I|R]) :-
    H =\= I,
    !,
    NextI is I + 1,
    missing([H|T], NextI, R).
missing([_|T], I, R) :-
    NextI is I + 1,
    missing(T, NextI, R).

для предиката без помощника.