Элементы расстояния в круговой матрице

Question

Это интересная проблема, с которой я столкнулся, что я считаю, должен иметь элегантное, доказуемое решение, но я не смог его получить. Я никогда определил его как:

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

Так f([a,b,d,c,a,d,k,a,d], 3) может вернуться [a,b,d,a,k,d,a,c,d], но f([a,b,d,c,a,d,k,a,d,a,a], 3) вернется null. Я определяю два элемента как R apart, если у них есть R-1 элементов между ними, поэтому в массиве [x,a,b,y], x и y находятся на расстоянии 3 друг от друга и 0 друг от друга.

Я чувствую, что это был бы отличный вопрос для интервью.

Answer 1

1. Разделить массив на группы одинаковых элементов (с сортировкой или использованием хеш-таблицы).
2. Найти самую большую группу. Если его размер больше floor(N/R), верните нуль.
3. Если размер самой большой группы равен точно N/R, перегруппируйте (частично отсортируйте) список групп, чтобы все группы размером N/R пришли первым на следующем шаге.
4. Для каждой группы поместите ее элементы в массив результатов (круговой буфер), увеличивая индекс на R, хотя это возможно. Если R и N не являются совместными, иногда - после N/GCD(N,R) приращений - индекс укажет на уже использованный элемент. В таких случаях индекс приращения на R+1 вместо R и продолжить.

Answer 2

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

Вот код, с результатами испытаний следующих:

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

public class ResolvingAlgo { 

public static Character[] resolver(Character[] objects, int R) { 
    //calculate frequency of each element 
    Map<Character, Integer> map = new HashMap<Character, Integer>(); 
    for (Character c : objects) { 
     Integer freq = map.get(c); 
     map.put(c, (freq == null) ? 1 : freq + 1); 
    } 
    //count elements with frequency R 
    List<Character> pillars = new ArrayList<Character>(); 
    for (Character c : map.keySet()) { 
     int freq = map.get(c); 
     if (R == freq) { 
      pillars.add(c); 
     } else if (objects.length/R < freq) { 
      return null; 
     } 
    } 
    //output array 
    Character output[] = new Character[objects.length]; 
    //load the pillars R+1 apart 
    int skip = (pillars.size()<R)?R:R+1; 
    for (Character c : pillars) { 
     int index = 0; 
     for (int out=index; out<output.length; out++) { 
      if (output[out] == null) { 
       break; 
      } 
      index++; 
     } 
     for (int i = R; i > 0; i--) { 
      output[index] = c; 
      index += skip; 
     } 
     map.remove(c); 
    }//pillars 
    //add remainders 
    while (!map.isEmpty()) { 
     int index = 0; 
     Character keyset[] = Arrays.copyOf(map.keySet().toArray(new Character[0]), map.size()); 
     for (Character c : keyset) { 
      for (int out = index; out < output.length; out++) { 
       if (null == output[out]) { 
        break; 
       } 
       index++; 
      } 
      output[index] = c; 
      int freq = map.get(c); 
      if (freq <= 1) { 
       map.remove(c); 
      } else { 
       map.put(c, freq - 1); 
      } 
     }//for keyset 
    }//while 
    return output; 
}//resolver 

public static void main(String... args) { 
    Character[][] input = { 
     {'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'd'}, 
     {'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'k'}, 
     {'a', 'a', 'a', 'b', 'c', 'd', 'd', 'd', 'k'}, 
     {'a', 'b', 'd', 'c', 'a', 'd', 'k', 'a', 'd', 'a', 'a'}, 
     {'a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd'}, 
     {'a', 'b', 'c', 'd', 'e', 'f', 'a', 'b', 'c', 'd', 'e', 'f'}, 
     {'a','b','c','d','a','b','c','d'} 
    }; 
    for(Character in[]: input) 
     System.out.println(Arrays.toString(resolver(in, 3))); 
} 
} 

Результат теста:

[d, b, c, a, d, b, c, a, d, b, c, a] 
[b, c, a, d, b, c, a, k, b, c, a, d] 
[d, a, b, d, a, c, d, a, k] 
null 
[b, c, d, b, c, a, b, c, d, a, a, a] 
[f, d, e, b, c, a, f, d, e, b, c, a] 
[d, b, c, a, d, b, c, a] 

Answer 3

Предупреждение: Это не решение. Это просто переформулировка.

Чтобы исправить обозначения, говорят, что m различные типы элементов (может также назвать то 1,2,...,m) и есть a_i элементы типа i. Тогда у нас есть a_1 + ... + a_m = N.

Пусть G(N,R) граф с вершинами v1, v2, ..., vN где есть ребро vi <--> vj когда |i-j| mod N < R. Например, G(N,2) представляет собой цикл N. Вопрос задает proper coloring из N -цикл с a_i вершинами цветных i.

В этом контексте вопрос эквивалентен вычислению ненулевых коэффициентов Stanley's chromatic symmetric function. Это может не облегчить проблему, но это, конечно, делает ее более интересной в моем сознании. Например, я считаю, что ответ известен для G(N,2), что-то вроде этого существует iff max(a_i) <= N/2 (конечно, нет решения, если оно есть a_i > N/R). Я обновлю этот ответ без дополнительных исследований.

Answer 4

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

Я отправляю это как ответ в основном потому, что я хочу опубликовать код для исправления. по-видимому, он имеет ту же проблему, что и более ранний ответ, поэтому, пожалуйста, кто-нибудь может объяснить, в чем проблема?

(ps в моем случае, группы также упорядочены по длине, что явно не указано ранее).

from collections import Counter, defaultdict 

def ring(n, text): 
    result = [None for t in text] 
    index = 0 
    for c in Counter(text).elements(): 
     while result[index] is not None: 
      index = (index + 1) % len(result) 
     result[index] = c 
     index = (index + n) % len(result) 
    loop = ''.join(result) 
    print(text, ' -> ', loop) 
    check(n, loop) 

def check(n, text): 
    loop = text + text 
    last = defaultdict(lambda: -n) 
    for (i,c) in enumerate(loop): 
     assert i - last[c] >= n, (c, i - last[c]) 
     last[c] = i 

ring(3, 'aaaabbbcccdd') # problematic according to B_? 
ring(3, 'abdcadkad') # given in question 
ring(3, 'abdcadkadaa') # given in question, expected to fail 

и работает:

> python3.2 ring.py 
aaaabbbcccdd -> acbacbacdabd 
abdcadkad -> akdacdabd 
abdcadkadaa -> aadakdacdab 
Traceback (most recent call last): 
    File "ring.py", line 25, in <module> 
    ring(3, 'abdcadkadaa') 
    File "ring.py", line 14, in ring 
    check(n, loop) 
    File "ring.py", line 20, in check 
    assert i - last[c] >= n, (c, i - last[c]) 
AssertionError: ('a', 1)