एक गोलाकार सरणी में तत्वों को स्थानांतरित करना

Question

यह एक दिलचस्प समस्या है जिसे मैंने पूरा किया है, मुझे लगता है कि मुझे एक सुरुचिपूर्ण, सिद्ध समाधान होना चाहिए, लेकिन मैं इसे प्राप्त करने में काफी सक्षम नहीं हूं।

एक समारोह है कि एन तत्वों और एक सकारात्मक पूर्णांक आर की एक सरणी इनपुट के रूप में लेता है, और रिटर्न एक परिपत्र सरणी (या किसी सरणी है कि आप के रूप में परिपत्र इलाज ) को परिभाषित करें, जहां कोई: मैं के रूप में परिभाषित किया है दो समान तत्व आर से कम हैं, या अगर कोई ऐसा आदेश संभव नहीं है तो शून्य।

तो 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 के बजाय R+1 द्वारा ऐसे मामलों में वृद्धि सूचकांक और जारी रखें।

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 तत्व हैं। फिर हमारे पास a_1 + ... + a_m = N है।

G(N,R)v1, v2, ..., vN के साथ ग्राफ हो, जहां किनारे है। उदाहरण के लिए, G(N,2)N-साइकिल है। प्रश्न N के लिए पूछता है-a_i रंगीन i के साथ चक्र।

इस संदर्भ में, प्रश्न Stanley's chromatic symmetric function के nonzero गुणांक की गणना करने के बराबर है। यह समस्या को और आसान नहीं बना सकता है, लेकिन यह निश्चित रूप से मेरे दिमाग में और अधिक रोचक बनाता है। उदाहरण के लिए, मेरा मानना ​​है कि उत्तर G(N,2) के लिए जाना जाता है, ऐसा कुछ है जैसे iff max(a_i) <= N/2 (निश्चित रूप से कोई समाधान मौजूद नहीं है यदि a_i > N/R)। मैं थोड़ी अधिक शोध के बाद इस गैर-उत्तर को अपडेट करूंगा।

Answer 4

मुझे खेद है, मैं यहाँ गूंगा महसूस कर रहा हूं, लेकिन मुझे Evgeny के समाधान पर आपत्तियों को समझ में नहीं आता है। मुझे लगता है कि नीचे दिया गया कोड लागू करता है जो वे सुझाते हैं (सिवाय इसके कि मैं वापस शून्य की बजाय त्रुटि फेंक देता हूं) और अनुक्रम के साथ ठीक काम करता है जो समस्याग्रस्त माना जाता है।

मैं इसे बड़े पैमाने पर उत्तर के रूप में पोस्ट कर रहा हूं क्योंकि मैं सुधार के लिए कोड पोस्ट करना चाहता हूं। संभवतः यह पहले के जवाब के समान समस्या है, तो कृपया कोई बता सकता है कि समस्या क्या है?

(मेरे मामले में पीएस, समूहों को भी लंबाई से आदेश दिया जाता है, जिसे स्पष्ट रूप से पहले नहीं दिया गया है)।

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)