Кратчайший способ получить уникальную последовательность в массиве

Question

У меня есть код JavaScript, который генерирует шаблон на основе массива.

Массив ниже:

[1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1]

вернет:

[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1]

Однако яхотите, чтобы шаблон был упрощен и получил только уникальную последовательность:

[1, 1, 1, 1, -1, -1, -1, -1]

Есть ли способ, которым я могу добиться этого с помощью slice() или filter()?Если нет, то какие-либо предложения о том, как я могу?

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

Answer 1

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

function getUniquePattern(pattern) {
    // Test an incrementally large slice of the original pattern.
    for (i = 0; i < pattern.length; i++) {
        // Take a slice to test
        var attempt = pattern.slice(0, i);

        // Check if the slice repeats perfectly against the pattern
        if(sliceIsRepeatable(attempt, pattern)){
            // Return the matched pattern
            return attempt;
        }
    }

    // Return an empty array for failures
    return [];
}

function sliceIsRepeatable(slice, pattern) {
    // Slice length must be a multiple of the pattern's length
    if(pattern.length % slice.length !== 0 ) return false;

    for (i = 0; i < pattern.length; i++) {
        j = i % slice.length;
        if(pattern[i] !== slice[j]) {
            return false;
        }
    }

    return true;
}

getUniquePattern([1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1]);

Answer 2

Не уверен, что это самый короткий путь, но он прост.И, надеюсь, легко следить, я разместил несколько комментариев, чтобы помочь показать, что он делает.

const test1 = [1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1];
const test2 = [4, -1, 4, -1, 4, -1, 4, -1];

function getSeq(a) {
  //lets try diving the array by length / 2, then each
  //time use bigger and bigger chunks.
  for (let chunks = a.length / 2; chunks >= 1; chunks --) {
    const chunksize = a.length / chunks;
    //can we divide equally?.    
    if (chunksize % 1 !== 0) continue;
    //lets compare all chunks are the same
    let found = true;
    for (let lpchunk = 1; lpchunk < chunks; lpchunk ++) {   
      for (let offset = 0; offset < chunksize; offset ++) {
        if (a[offset] !== a[offset + lpchunk * chunksize]) {
          found = false;
          break;
        }
      }
    }
    //we have found a duplicate lets return..
    if (found) {
      const dups = [];
      for (let offset = 0; offset < chunksize; offset ++) {
        dups.push(a[offset]);
      }
      return dups;
    }
  }
}

console.log(getSeq(test1).join(", "));
console.log(getSeq(test2).join(", "));

Answer 3

Извините, насчет другого ответа.Я был быстр.

// Ask the original sequence as parameter
function uniqueSequence(originalSequence){

    return 
        originalSequence
        .map(function(value, index){                            // Get difference between each number.
            return value - originalSequence[index - 1];         // Somthing like [1,2,3,2,1] => [NaN, 1,1,-1,-1]
        })
        .toString()                                             // Parse that result to string format => "NaN,1,1,-1,-1"
        .match(/N((,[0-9-]+)*?)\1*$/)[1]                        // we look for the shortest pattern of comma-separated integers 
                                                                // (,\d+) starting right after "NaN" and repeating till 
                                                                // the end of the string. Result in something like => ",1,1,-1,-1"
        .substring(1)                                           // Remove the first comma => "1,1,-1,-1"                                    
        .split(',')                                             // Convert to array ["1","1","-1","-1"]
        .map(function(value){
            return parseInt(value);                             // Parse each element to integer [1,1,-1,-1]
        });
}

В кратчайшем коде (ES6)

 f=_=>_.map((a,i)=>a-_[i-1]).toString().match(/N((,[0-9-]+)*?)\1*$/)[1].substring(1).split`,`.map(a=>~~a)

f=_=>_.map((a,i)=>a-_[i-1]).toString().match(/N((,[0-9-]+)*?)\1*$/)[1].substring(1).split`,`.map(a=>~~a)

// Ask the original sequence as parameter
function uniqueSequence(originalSequence){

    return originalSequence
        .map(function(value, index){                            // Get difference between each number.
            return value - originalSequence[index - 1];         // Somthing like [1,2,3,2,1] => [NaN, 1,1,-1,-1]
        })
        .toString()                                             // Parse that result to string format => "NaN,1,1,-1,-1"
        .match(/N((,[0-9-]+)*?)\1*$/)[1]                       // we look for the shortest pattern of comma-separated integers 
                                                                // (,\d+) starting right after "NaN" and repeating till 
                                                                // the end of the string. Result in something like => ",1,1,-1,-1"
        .substring(1)                                           // Remove the first comma => "1,1,-1,-1"                                    
        .split(',')                                             // Convert to array ["1","1","-1","-1"]
        .map(function(value){
            return parseInt(value);                             // Parse each element to integer [1,1,-1,-1]
        });
}

console.log(f([1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1]))
console.log(uniqueSequence([1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1]))