Javascript: узнать даты окончания

Рассмотрим этот вложенный массив дат и имен:

var fDates = [
    ['2015-02-03', 'name1'],
    ['2015-02-04', 'nameg'],
    ['2015-02-04', 'name5'],
    ['2015-02-05', 'nameh'],
    ['1929-03-12', 'name4'],
    ['2023-07-01', 'name7'],
    ['2015-02-07', 'name0'],
    ['2015-02-08', 'nameh'],
    ['2015-02-15', 'namex'],
    ['2015-02-09', 'namew'],
    ['1980-12-23', 'name2'],
    ['2015-02-12', 'namen'],
    ['2015-02-13', 'named'],
]

Как я могу определить те даты, которые не соответствуют последовательности. Меня не волнует, повторяются ли даты или пропущены, мне просто нужны не по порядку. То есть, я должен вернуться:

results = [
    ['1929-03-12', 'name4'],
    ['2023-07-01', 'name7'],
    ['2015-02-15', 'namex'],
    ['1980-12-23', 'name2'],
]

('Namex' менее очевидно, но это не в общем порядке списка.)

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

Случай использования. Я отсортировал и устарел записи, и вам нужно найти те, где даты "подозрительны" - возможно, ошибка ввода - для отметки для проверки.

NB1: Я использую прямой Javascript и НЕ структуру. (Я нахожусь в узле, но я ищу решение без пакетов, чтобы я мог понять, что происходит...)

Ответ 1

Здесь адаптация LIS Rosetta Code для выполнения пользовательских функций getElement и compare. Мы можем уточнить функции сравнения и элемента-get, исходя из ваших конкретных потребностей.

function f(arr, getElement, compare){
  function findIndex(input){
    var len = input.length;
    var maxSeqEndingHere = new Array(len).fill(1)
    for(var i=0; i<len; i++)
      for(var j=i-1;j>=0;j--)
        if(compare(getElement(input, i), getElement(input, j)) && maxSeqEndingHere[j] >= maxSeqEndingHere[i])
          maxSeqEndingHere[i] = maxSeqEndingHere[j]+1;
    return maxSeqEndingHere;
  }

  function findSequence(input, result){
    var maxValue = Math.max.apply(null, result);
    var maxIndex = result.indexOf(Math.max.apply(Math, result));
    var output = new Set();
    output.add(maxIndex);
    for(var i = maxIndex ; i >= 0; i--){
      if(maxValue==0)break;
      if(compare(getElement(input, maxIndex), getElement(input, i))  && result[i] == maxValue-1){
        output.add(i);
        maxValue--;
      }
    }

    return output;
  }

  var result = findIndex(arr);
  var final = findSequence(arr, result)
  return arr.filter((e, i) => !final.has(i));
}

var fDates = [
    ['2015-02-03', 'name1'],
    ['2015-02-04', 'nameg'],
    ['2015-02-04', 'name5'],
    ['2015-02-05', 'nameh'],
    ['1929-03-12', 'name4'],
    ['2023-07-01', 'name7'],
    ['2015-02-07', 'name0'],
    ['2015-02-08', 'nameh'],
    ['2015-02-15', 'namex'],
    ['2015-02-09', 'namew'],
    ['1980-12-23', 'name2'],
    ['2015-02-12', 'namen'],
    ['2015-02-13', 'named'],
];

console.log(f(fDates, (arr, i) => arr[i][0], (a,b) => a >= b));

Ответ 2

Это решение пытается получить все допустимые последовательности и возвращает длинные последовательности для фильтрации частей.

Он работает путем итерации заданного массива и проверяет, могут ли значения построить последовательность. Если задано значение, то в результате частичного результата имеет действительный предшественник, массив добавляется с этим значением. Если не выполняется обратное отслеживание и поиск последовательности выполняется с действительным предшественником.

act.   array
value   7  3  4  4  5  1 23  7   comment
-----  ------------------------  ---------------------------
   7    7                        add array with single value

   3    7                        keep
           3                     add array with single value

   4    7                        keep
           3  4                  add value to array

   4    7                        keep
           3  4  4               add value to array

   5    7                        keep
           3  4  4  5            add value to array

   1    7                        keep
           3  4  4  5            keep
                       1         add array with single value

  23    7                23      add value to array
           3  4  4  5    23      add value to array
                       1 23      add value to array

   7    7                23      keep
        7                    7   fork above, filter for smaller or equal and add value
           3  4  4  5    23      keep
           3  4  4  5        7   fork above, filter for smaller or equal and add value
                       1 23      keep
                       1     7   fork above, filter for smaller or equal and add value

function longestSequences(array, getValue = v => v) {
    return array
        .reduce(function (sub, value) {
            var single = true;

            sub.forEach(function (s) {
                var temp;

                if (getValue(s[s.length - 1]) <= getValue(value)) {
                    s.push(value);
                    single = false;
                    return;
                }

                // backtracking
                temp = s.reduceRight(function (r, v) {
                    if (getValue(v) <= getValue(r[0])) {
                        r.unshift(v);
                        single = false;
                    }
                    return r;
                }, [value]);

                if (temp.length !== 1 && !sub.some(s => s.length === temp.length && s.every((v, i) => getValue(v) === getValue(temp[i])))) {
                    sub.push(temp);
                }
            });

            if (single) {
                sub.push([value]);
            }
            return sub;
        }, [])
        .reduce(function (r, a) {
            if (!r || r[0].length < a.length) {
                return [a];
            }
            if (r[0].length === a.length) {
                r.push(a);
            }
            return r;
        }, undefined);
}

function notInSequence(array, getValue = v => v) {
    var longest = longestSequences(array, getValue);
    return array.filter((i => a => a !== longest[0][i] || !++i)(0));
}

var array = [7, 3, 4, 4, 5, 1, 23, 7, 8, 15, 9, 2, 12, 13],
    fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
    usuallyFailingButNotHere = [['2015-01-01'], ['2014-01-01'], ['2015-01-02'], ['2014-01-02'], ['2015-01-03'], ['2014-01-03'], ['2014-01-04'], ['2015-01-04'], ['2014-01-05'], ['2014-01-06'], ['2014-01-07'], ['2014-01-08'], ['2014-01-09'], ['2014-01-10'], ['2014-01-11']],
    test2 = [['1975-01-01'], ['2015-02-03'], ['2015-02-04'], ['2015-02-04'], ['2015-02-05'], ['1929-03-12'], ['2023-07-01'], ['2015-02-07'], ['2015-02-08']];

console.log(longestSequences(array));
console.log(notInSequence(array));

console.log(notInSequence(fDates, a => a[0]));

console.log(longestSequences(usuallyFailingButNotHere, a => a[0]));
console.log(notInSequence(usuallyFailingButNotHere, a => a[0]));

console.log(longestSequences(test2, a => a[0]));
console.log(notInSequence(test2, a => a[0]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Ответ 3

Это решение использует функцию reduce и сохраняет ранее принятую дату для проведения необходимых сравнений.

var fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
results = fDates.reduce((acc, c, i, arr) => {
  /*
   * This function finds a potential valid sequence.
   * Basically, will check if any next valid sequence is
   * ahead from the passed controlDate.
   */
  function sequenceAhead(controlDate) {
    for (var j = i + 1; j < arr.length; j++) {
      let [dt] = arr[j];
      //The controlDate is invalid because at least a forward date is in conflict with its sequence.
      if (dt > acc.previous && dt < controlDate) return true; 
    }
    
    //The controlDate is valid because forward dates don't conflict with its sequence.
    return false; 
  }
  
  let [date] = c; //Current date in this iteration.
  if (i > 0) { // If this is not the first iteration
    if (date === acc.previous) return acc; // Same as previous date are skipped.
    // If the current date is lesser than previous then is out of sequence.
    // Or if there is at least valid sequence ahead.
    if (date < acc.previous || sequenceAhead(date)) acc.results.push(c); 
    else acc.previous = date; // Else, this current date is in sequence.
  } 
  else acc.previous = date; // Else, set the first date.

  return acc;
}, { 'results': [] }).results;

console.log(results);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Ответ 4

Все предыдущие ответы сосредоточены на JavaScript и, возможно, они не будут работать корректно. Поэтому я решил добавить новый ответ, посвященный алгоритму.

Как @Trees4theForest отметил в своем вопросе и комментариях, он ищет решение для Longest Увеличения подпоследовательности и out of order dates являются даты, которые не Longest Увеличения подпоследовательности (LIS) набора.

Я использовал этот метод, как показано ниже. В алгоритме это верно.

function longestIncreasingSequence(arr, strict) {

    var index = 0,
        indexWalker,
        longestIncreasingSequence,
        i,
        il,
        j;

    // start by putting a reference to the first entry of the array in the sequence
    indexWalker = [index];

    // Then walk through the array using the following methodolgy to find the index of the final term in the longestIncreasing and
    // a sequence (which may need altering later) which probably, roughly increases towards it - http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
    for (i = 1, il = arr.length; i < il; i++) {

        if (arr[i] < arr[indexWalker[index]]) {

            // if the value is smaller than the last value referenced in the walker put it in place of the first item larger than it in the walker
            for (j = 0; j <= index; j++) {

                // As well as being smaller than the stored value we must either 
                // - be checking against the first entry
                // - not be in strict mode, so equality is ok
                // - be larger than the previous entry
                if (arr[i] < arr[indexWalker[j]] && (!strict || !j || arr[i] > arr[indexWalker[j - 1]])) {
                    indexWalker[j] = i;
                    break;
                }
            }

            // If the value is greater than [or equal when not in strict mode) as the last in the walker append to the walker
        } else if (arr[i] > arr[indexWalker[index]] || (arr[i] === arr[indexWalker[index]] && !strict)) {
            indexWalker[++index] = i;
        }

    }

    // Create an empty array to store the sequence and write the final term in the sequence to it
    longestIncreasingSequence = new Array(index + 1);
    longestIncreasingSequence[index] = arr[indexWalker[index]];


    // Work backwards through the provisional indexes stored in indexWalker checking for consistency
    for (i = index - 1; i >= 0; i--) {

        // If the index stored is smaller than the last one it valid to use its corresponding value in the sequence... so we do  
        if (indexWalker[i] < indexWalker[i + 1]) {
            longestIncreasingSequence[i] = arr[indexWalker[i]];

            // Otherwise we need to work backwards from the last entry in the sequence and find a value smaller than the last entry 
            // but bigger than the value at i (this must be possible because of the way we constructed the indexWalker array)
        } else {
            for (j = indexWalker[i + 1] - 1; j >= 0; j--) {
                if ((strict && arr[j] > arr[indexWalker[i]] && arr[j] < arr[indexWalker[i + 1]]) ||
                    (!strict && arr[j] >= arr[indexWalker[i]] && arr[j] <= arr[indexWalker[i + 1]])) {
                    longestIncreasingSequence[i] = arr[j];
                    indexWalker[i] = j;
                    break;
                }
            }
        }
    }

    return longestIncreasingSequence;
}

С помощью метода выше мы можем найти даты, которые не соответствуют порядку, как показано ниже:

// Finding Longest Increase Subsequence (LIS) set
var _longestIncreasingSequence = longestIncreasingSequence(fDates.map(([date]) => date)); 

// Out of order dates
var result = fDates.filter(([date]) => !_longestIncreasingSequence.includes(date));

Демо-версия онлайн (jsFiddle)

Ответ 5

вот простое self- объяснительное решение. надеюсь, это поможет вам.

const findOutOfSequenceDates = items => {
    items = items.map(d => d);

    const sequence = [], outOfsequence = [];
    sequence.push(items.shift());

    const last = ind => sequence[sequence.length - ind][0];

    items.forEach(item => {
        const current = new Date(item[0]);

        if (current >= new Date(last(1))) {
            sequence.push(item);
        } else if (current >= new Date(last(2))) {
            outOfsequence.push(sequence.pop());
            sequence.push(item);
        } else {
            outOfsequence.push(item);
        }
    });

    return outOfsequence;
};

var fDates = [
    ['2015-02-03', 'name1'],
    ['2015-02-04', 'nameg'],
    ['2015-02-04', 'name5'],
    ['2015-02-05', 'nameh'],
    ['1929-03-12', 'name4'],
    ['2023-07-01', 'name7'],
    ['2015-02-07', 'name0'],
    ['2015-02-08', 'nameh'],
    ['2015-02-15', 'namex'],
    ['2015-02-09', 'namew'],
    ['1980-12-23', 'name2'],
    ['2015-02-12', 'namen'],
    ['2015-02-13', 'named'],
];
console.log(findOutOfSequenceDates(fDates));

Ответ 6

Используйте тип даты Javascript. Сравните с этими объектами. Очень упрощенно,

date1 = new Date(fDates[i, 0])
date2 = new Date(fDates[i+1, 0])
if (date2 < date1) {    // or whatever comparison you want ...
    // flag / print / alert the date
}

Чтобы прояснить, это просто находит предметы не в порядке. Вы можете сделать это со строками, как указал Jaromanda X Однако вы используете фразу "выход из строя"; что бы это ни значило для вас, Date должна дать вам возможность определить и проверить ее. Например, "2023-07-01" неприемлемо, потому что он находится на расстоянии 8 лет или просто потому, что он не соответствует срокам 2015 года? Вам может потребоваться некоторое сравнение с более простым временным интервалом, например, один месяц, где ваше сравнение будет выглядеть примерно так:

if (date2-date1 > one_month)

Ответ 7

Резюме вашего вопроса Если я правильно понял ваш вопрос, вы пытаетесь идентифицировать записи массива, которые не соответствуют хронологическому порядку, основанному на значении свойства времени и даты.

Решение Преобразование строки/времени даты в метку времени UNIX (количество секунд, прошедших с 01/jan/1970 в 00:00:00)

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

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

Пример кода

var arrData = [
    {date: '2015-02-03', value:'name1'},
    {date: '2015-02-04', value:'nameg'},
    {date: '2015-02-04', value:'name5'},
    {date: '2015-02-05', value:'nameh'},
    {date: '1929-03-12', value:'name4'},
    {date: '2023-07-01', value:'name7'},
    {date: '2015-02-07', value:'name0'},
    {date: '2015-02-08', value:'nameh'},
    {date: '2015-02-15', value:'namex'},
    {date: '2015-02-09', value:'namew'},
    {date: '1980-12-23', value:'name2'},
    {date: '2015-02-12', value:'namen'},
    {date: '2015-02-13', value:'named'}
];

var arrSeqErrors = [];
function funTestDates(){
  var intLastValue = 0, intUnixDate =0;
  for (x = 0; x <= arrData.length-1; x++){
    intUnixDate = Date.parse(arrData[x].date)/1000;
    var intResult = intUnixDate - intLastValue;
    if (intResult < 0){
      console.log("initeneration: " + x + " is out of sequence");
      arrSeqErrors.push (arrData[x]);
    }
    intLastValue = intResult;
  }
  console.log("Items out of sequence are:");
  console.log(arrSeqErrors);
}

funTestDates();