raiden4589
BAN USERI have tweak the code a bit
package com.algorithms;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class GoogleSequence {
public class Seq {
private LinkedList<LinkedList<Integer>> sets;
public LinkedList<LinkedList<Integer>> getSets() {
return sets;
}
public Seq(LinkedList<LinkedList<Integer>> sets) {
this.sets = sets;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return sets.toString();
}
}
public LinkedList<Seq> calculate(int N, int M, int K, int L) {
// pos seq of N
// with M runs
// nums in seq <= K
// adj diff <=L
LinkedList<LinkedList<Integer>> lists = new LinkedList<LinkedList<Integer>>();
// Get all combinations of sequnces up to N
for (int j = 0; j < N; j++) {
int size = lists.size();
// If lists is empty add the first up to K numbers
if (size == 0) {
for (int i = 1; i <= K; i++) {
LinkedList<Integer> newL = new LinkedList<Integer>();
newL.add(i);
lists.add(newL);
}
}
LinkedList<Integer> list = null;
// Iterate up to the current size of the list.
// Add up to K to the end of each sublist
// The iterations follow this pattern,
// 1,2,3,4,... K
// 11,21,31,41,12,22,...,13,23.....K1
for (int s = 0; s < size; s++) {
list = lists.get(s);
LinkedList<Integer> newL = new LinkedList<Integer>(list);
for (int i = 1; i <= K; i++) {
LinkedList<Integer> temp = new LinkedList<Integer>();
if (i == 1) {
list.offerLast(i);
} else {
temp.addAll(newL);
temp.offerLast(i);
lists.offerLast(temp);
}
}
}
}
LinkedList<Integer> pk = lists.peekLast();
LinkedList<Seq> finalLists = new LinkedList<Seq>();
for (LinkedList<Integer> list : lists) {
int index = 0;
LinkedList<LinkedList<Integer>> sets = new LinkedList<LinkedList<Integer>>();
while (list.size() > 0 && (index + 1) < list.size()) {
int prev = list.get(index);
int next = list.get(index + 1);
//Check if pattern exists , if it doesnt then add the new set
if (prev + L != next && prev - L != next) {
List<Integer> sub = list.subList(0, index + 2);
sets.add(new LinkedList<Integer>(sub));
if (list.size() >= index+1) {
list = new LinkedList<Integer>(list.subList(index+1 ,
list.size()));
index = 0;
if (list.size()==1) {
sets.add(new LinkedList<>(list));
}
}
} else {
index++;
if (index + 1 == list.size() || list.size()==1) {
sets.add(new LinkedList<>(list));
}
}
}
if (sets.size() == M) {
finalLists.add(new Seq(new LinkedList<LinkedList<Integer>>(sets)));
}
}
return finalLists;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
GoogleSequence seq = new GoogleSequence();
System.out.println("Type four numbers, N M K L");
LinkedList<Seq> lists = seq.calculate(sc.nextInt(), sc.nextInt(),
sc.nextInt(), sc.nextInt());
System.out.println("POSSIBLE:" + lists.size());
for (Seq linkedList : lists) {
System.out.println(linkedList.toString());
}
}
}
Well from what I understood the question wanted you to find all sequence of numbers that met the four criteria. For example N=5, M=3, K=9,L=1. N stands for the length of the sequences, therefore here each sequence has 5 elements. What I did was calculate all combinations of sequences 11111,11112,11113.... up to K,K,K,K,K . K stands for the maximum number for each element. After finding all combinations I split each one to sets where each set would be 1+L, 1+L+L.... or 5-L,5-L-L.. Here L is 1 so sets for this sequence (1,2,3,4,5,8,7,6,4,3,2,1) this sequence is more than 5 but just to explain it. Sets would be 1,2,3,4,5,8 8,7,6 4,3,2,1, So we have 3 sets for this sequence. M is 3 so it would be a match. M stands for the number of sets in each sequence. :)
- raiden4589 March 23, 2012
- raiden4589 March 23, 2012