Найти последовательные наименьшие суммы кратных трех различных чисел, JavaScript

Question

На this post я нашел алгоритм для определения яркости в цвета RGB:

Luminance (стандарт для определенных цветовых пространств): (0.2126 * R + 0,7152 * G + 0,0722 * B)

Я хочу использовать это уравнение, начиная с rgb(0,0,0), чтобы произвести все цвета RGB в порядке от самого низкого до самого высокой яркости, а затем обратить их в 4096x4096 холст.

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

Так, например, начиная с и RGB из 0,0,0, яркости будет 0 (0.2126*0 + 0.7152*0 + 0.0722*0 = 0), следующий минимумом люминесцентного значение RGB будет 0,0,1 потому 0.2126*0 + 0.7152*0 + 0.0722*1 = .0722, и нет никакого набора кратных, что бы суммировать к меньшему числу.

Первые 19 последовательных значений яркости будет выглядеть следующим образом (я, возможно, пропустили один или два, потому что я вычислил их вручную, но, надеюсь, это помогает сделать точку):

RGB  =>  Luminence 

0,0,0  =>  0 
0,0,1  =>  .0722 
0,0,2  =>  .1444 
1,0,0  =>  .2126 
0,0,3  =>  .2166 
1,0,1  =>  .2848 
0,0,4  =>  .2888 
1,0,2  =>  .357 
0,0,5  =>  .361 
2,0,0  =>  .4252 
1,0,3  =>  .4292 
0,0,6  =>  .4332 
2,0,1  =>  .4974 
1,0,4  =>  .5014 
0,0,7  =>  .5054 
2,0,2  =>  .5696 
1,0,5  =>  .5736 
0,0,8  =>  .5776 
3,0,0  =>  .6378 

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

EDIT: Я сделал несколько дополнительных исследований, и похоже, что решение может заключаться в использовании линейных диофантовых уравнений. Если я беру каждое десятичное число и умножаюсь на 1000, получаю 2126, 7152, & 722. Затем подсчитывайте 1 на 1 до 2,550,000 (2126*255 + 7152*255 + 722*255), я могу проверить каждое число, чтобы узнать, является ли это решением уравнения 2126r + 7152g + 722b = n, где n - это текущее число, отсчитываемое до, и r, g, & b - неизвестные. Если бы я мог это сделать, я мог бы вычислить все возможные значения rgb при следующем значении последовательной яркости, даже не удваивая значения для значений повторяющейся яркости, и мне нужно было бы выполнить 2,55 миллиона вычислений вместо 16,77+ миллионов (по одному для каждого цвета). Если кто-нибудь знает, как закодировать это уравнение, или если у кого-нибудь есть лучшее решение, я был бы очень благодарен. Благодаря!

Answer 1

Вот алгоритм (забыли его название) для вашей проблемы: Алгоритм может отображать все цветовые кортежи {R, G, B}, отсортированные в определенном порядке. В вашем случае это по яркости по возрастанию: цвет1 < цвет2 < ==> е (цвет1) < е (цвет2), где F (цвет) = 0,2126 * R + 0,7152 * G + 0,0722 * B

• Initialize: обр = [{г: 0, г: 0, Ь: 0}] (минимальный цвет)
• Повтор:
  • Выбор мин (Ir): а [Ir] = {Rr < 255, Gr, bR} и cR = {rR + 1, gR, bR}> arr [i] для каждого i. (Выберите первый цвет в arr таким образом, что если мы добавим 1 к его компоненте r, мы получим новый цвет, который больше, чем все цвета в настоящее время в arr)
  • Аналогичные для iG и iB => также получают cG = { Р.Г., Gg + 1, Bg} и сВ = {гв, дв, ББ + 1}
  • Среди Сr, Cg и сВ выбора минимального цвета гр
  • Append гр в массив обр

Алгоритм останавливается, когда нет таких iR, iG или iB.

Примечания:

• обр всегда в отсортированном (по возрастанию) порядке, потому что каждый раз, когда новый цвет добавляется к обр, это всегда больше, чем каждый элементов в настоящее время в обр.
• Поскольку обр в порядке возрастания, мы только сравнить СR/Cg/Cb с последним элементом обр, чтобы проверить, если это больше, чем каждые элементы обр
• Ir, Ig и И.Б. увеличить с помощью алгоритма
• Сложность O (N) с N количеством цветов (2^24) ~ 16M. С помощью алгоритма с кучей сложность составляет около O (NlogN).

Вот моя реализация (проверено в nodejs 6)

// use integer to avoid floating point inaccuracy 
const lumixOf = {r: 2126, g: 7152, b: 722}; 

const maxValue = 256; 
const components = ['r', 'g', 'b']; 

class Color { 
    constructor(r, g, b, lum) { 
    this.r = r; 
    this.g = g; 
    this.b = b; 
    this.lum = lum; 
    } 

    add(component) { 
    const ans = new Color(this.r, this.g, this.b, this.lum); 
    if (++ans[component] >= maxValue) return null; // exceed 255 
    ans.lum += lumixOf[component]; 
    return ans; 
    } 

    greater(color2) { 
    // return this.lum > color2.lum; 
    if (this.lum !== color2.lum) return this.lum > color2.lum; 
    if (this.r !== color2.r) return this.r > color2.r; 
    if (this.g !== color2.g) return this.g > color2.g; 
    return this.b > color2.b;   
    } 
} 

let a = [new Color(0, 0, 0, 0)]; // R, G, B, lumix 
let index = {r: 0, g: 0, b: 0}; 

console.log('#0:', a[0]); 
// Test: print the first 100 colors 
for (let count = 1; count < 100; ++count) { 
    let nextColor = null; 
    const len = a.length; 
    const currentColor = a[len - 1]; 
    components.forEach(component => { 
    let cIndex = index[component]; 
    for (; cIndex < len; ++cIndex) { 
     const newColor = a[cIndex].add(component); 
     if (!newColor || !newColor.greater(currentColor)) continue; 

     // find the minimum next color 
     if (nextColor == null || nextColor.greater(newColor)) { 
     nextColor = newColor; 
     } 
     break; 
    } 
    index[component] = cIndex; 
    }); 

    if (!nextColor) break; // done. No more color 
    a.push(nextColor); 
    console.log('#' + count + ':', nextColor); 
} 
console.log(a.length); 

Этот список реализации всех 2^24 = 16777216 цветов (как только вы удалите условие count < 100 в главном цикле, но вы не хотите распечатать так много строк). Если некоторые цвета имеют одинаковое значение яркости, они затем сортируются по их значению R, затем по значению G, затем по значению B. Если вам нужен только один цвет для каждого значения яркости, раскомментируйте первую строку в функции greater() - тогда вы получите 1207615 цветов с четкой яркостью

Answer 2

Один факт, который вы можете использовать, состоит в том, что каждый триплет в последовательности будет иметь значение R, G или B только на один больше, чем триплет, который уже был выведен.

Таким образом, можно поддерживать BinaryHeap (отсортированных по яркости), содержащий все триплеты, которые являются 1 больше в R, G или В, чем триплет, который уже был выход, и сделать это в цикле:

• Удалить наименьший элемент (R, G, B) из кучи
• Выход это
• Добавить (г + 1, г, б), (г, г + 1, б) и (г, г, b + 1) в кучу, но только если они действительны триплеты (все значения меньше или равны 255) и только если они еще не находятся в куче. Триплет не будет находиться в куче, если альтернативные триплеты, которые он мог бы генерировать из (1 меньше в r, g или b, в пределах разрешенных границ), имеют более высокую яркость, чем (r, g, b).

, например, только добавить (г + 1, г, б) если (г + 1, г-1, б) имеет более высокую яркость, чем (г, г, б) или (г + 1, г -1, b) недействительна. Поскольку коэффициенты вычисления яркости на основе r, g, b фиксированы, (r + 1, g-1, b) всегда будут иметь меньшую яркость, и вы должны добавить (r + 1, g, b), если (г + 1, г-1, б) является недействительным, что, когда г = 0.

В псевдокоде правила так:

function addTriplets(r, g, b) 
{ 
    if(g < 255) 
     pushTripletToHeap(r, g + 1, b); 
    if((g == 0) && (r < 255)) 
     pushTripletToHeap(r + 1, g, b); 
    if((g == 0) && (r == 0) && (b < 255)) 
     pushTripletToHeap(r, g, b + 1); 
} 

Нажмите на (0, 0, 0) триплет на кучу перед запуском цикла и остановить цикл, когда куча пуста.

Answer 3

Извините, но я должен сказать, что вы делаете расточительную работу.

8-битное квантование RGB даст 16.7M цветов с 256 уровнями яркости (включая черно-белый). Однако у вас недостаточно пикселей, чтобы отобразить их все на мониторе 4K, который имел бы 3840 x 2160 = 8294400 пикселей на стандарте 4K TV или как 4096 x 2160 = 8847360 на стандарте 4K фильмов. Кроме того, что означает, что образец 1 пикселя цвета глаз, особенно на дисплее 4K ..?

Я бы рекомендовал вам использовать 7 бит квантования вместо 8 бит. Это даст вам образцы образцов 2^21 => 2097152, и они будут отображаться как одиночный пиксель на мониторе HD/телевизоре и 2x2 пикселах на мониторе/телевизоре 4K. Красивый.

Код будет следующим:

"use strict"; 
 
var allColors = Array(Math.pow(2,21)),   // All 2^21 colors 
 
     cgbl = Array(128).fill().map(e => []); // Colors gropuped by luminance 
 
for (var i = 0, len = allColors.length; i < len; i++) allColors[i] = [i>>14, (i&16256)>>7, i&127]; 
 
allColors.reduce((g,c) => (g[Math.round(c[0]*0.2126 + c[1]*0.7152 + c[2]*0.0722)].push(c),g), cgbl); 
 
cgbl.forEach((y,i) => console.log(y.length,"Colors at luminance level:",i));

Однако помните, что ваши значения RGB теперь в 7 битном квантовании. Поскольку мы уже сгруппировали их на 128 уровней яркости, я также посоветую вам сопоставить все значения RGB в группах яркости (вспомогательные массивы) обратно на 8 бит, сдвинув их значения на 1 бит (r << 1; g << 1; b << 1;) перед их отображением. Используя функтор .map(), это тривиальная работа.

Answer 4

Поскольку мой первоначальный ответ уже давно, я сделать этот ответ уточнить алгоритм, так как OP запросила

Рассмотрим аналогичную задачу (но легче рассуждать о):

• Пусть A - множество чисел в порядке возрастания, у которых нет другого простого множителя, чем 2, 3 и 5 (Ai = 2^x * 3^y * 5^z)
• Найти n-е число A

Sure A1 = 1 = 2^0 * 3^0 * 5^0

Предположим, что на каком-то этапе мы вычислили A1 .., И мы должны найти [п + 1]

• Если А [п + 1] делится на 2, то А [п + 1] = A [i2] * 2 с 1 < = i2 < = п
• Если А [п + 1] делится на 3, то А [п + 1] = A [i3] * 3 с 1 < = i3 < = п
• Если А [п + 1] делится на 5, то а [п + 1] = A [i5] * 5 с 1 < = i5 < = п

(и, очевидно, а [п + 1] делится на, по меньшей мере один из них)

Доказательство: A[n+1] = 2^x * 3^y * 5^z. Если A [n + 1] делится на 2, то x> 0, поэтому B = A[n+1]/2 = 2^(x-1) * 3^y * 5^z должно быть в A. И поскольку B < A [n + 1], он должен быть до A [n + 1] в A, поэтому B = A [i2], с 1 < = i2 < = n.

Итак, чтобы найти [п + 1], мы можем:

• Найти минимальное i2, что A [i2] * 2> A [п]
• Похожие на i3 и i5
• ==> A [n + 1] = min (A [i2] * 2, A [i3] * 3, A [i5] * 5)

Имея A1 = 1, выполните следующие шаги (n - 1), и мы найдем n-е число A

Теперь, если на каждом Итерационный поиск A [n + 1], мы используем 3 для петель от 1 до n для вычисления i2, i3 и i5, временной сложностью будет O (N^2). Но вы можете видеть, что i2, i3 и i5 для каждой итерации никогда не уменьшаются (меньше, чем это значение для предыдущей итерации, соответственно). Таким образом, мы можем сохранить эти i2, i3 и i5 значения, и на каждой итерации нужно:

while (A[i2]*2 <= A[n]) ++i2; 
while (A[i3]*3 <= A[n]) ++i3; 
while (A[i5]*5 <= A[n]) ++i5; 

Теперь временная сложность становится O (N): в то время как while петли еще вложенными в главном for 1->n цикле , существует только 4 переменных, возрастающих от 1 -> n, и их можно рассматривать как 4 независимых цикла. Вы можете проверить свойство (N) на O, используя часы и измерить время выполнения для различных N s

Применение этого алгоритма к вашей проблеме:

• 2, 3 и 5 становится R, G и B
• Целочисленное сравнение будет функцией сравнения цветов, которую вы определяете
• Если вам нужно перечислить все цвета 2^24, определите функцию сравнения, чтобы не было 2 одинаковых цвета (если C1 и C2 являются 2 разными цветами, то либо C1 < C2 или C2 < C1) - как я сделал в оригинальном ответе