Boa noite,
Recentemente, tentei fazer um desafio de programação que dizia o seguinte:
Dado um alfabeto de 4 letras (A, C, G, T).
Formar 96 palavras de 6 letras cada uma.
Cada palavra deve ser diferente de todas as outras palavras em no mínimo 3 posições.
Não consegui achar 96, apenas 64 palavras por meio de combinação. Podem ajudar?
Parece interessante. Mostra aí como você fez.
Esse codigo so retorna 64 palavras.
/** Length of the word */
private static final int WORD_LENGTH = 6;
/** The words most differ in at least 3 positions */
private static final int MINIMUM_CHAR_DIFFERENCE = 3;
/** Newly created word */
private final char[] newWord = new char[WORD_LENGTH];
/** List with the filtered items */
private final List<String> words = new ArrayList<>();
/**
* Generates all possible combinations and adds it to the permutations list if the generated word is valid
* @param validChars dictionary of possible chars
*/
private void combine(char[] validChars) {
combine(validChars,0);
}
/**
* Generates all possible combinations and adds it to the permutations list if the generated word is valid
* @param validChars dictionary of possible chars
* @param position next position
*/
private void combine(char[] validChars, int position) {
if (position == newWord.length) {
addToList(newWord);
} else {
for (char validChar : validChars) {
newWord[position] = validChar;
combine(validChars, position + 1);
}
}
}
/**
* Add the word to the complete list
*/
private void addToList(char[] newWord) {
String word = charArrayToString(newWord);
if (isWordValid(word)) {
words.add(word);
}
}
/**
* Convert char array to String
* @param word char array to be converted
* @return a String formed by the char array
*/
private String charArrayToString(char[] word) {
return String.valueOf(word);
}
/**
* Check char by char if the new word does not match the added ones in 3 or more positions
* @param newWord new word
* @return true if the new word has minimum of 3 differences compared to other words
*/
private boolean isWordValid(String newWord) {
//Iterate the list of words
for(String word : words) {
int charCounter = getNumberOfDifferentChars(word, newWord);
//The counter is bigger or equal than 3, which means the word is valid.
if(charCounter <= MINIMUM_CHAR_DIFFERENCE) {
return false;
}
}
return true;
}
/**
* Compare two strings and return the number of different positions between them
* @param word to be compared
* @param newWord to be compared
* @return number of different positions between them
*/
private int getNumberOfDifferentChars(String word, String newWord) {
int charCounter = 0;
//Iterate the chars from each word
for(int i = 0; i < WORD_LENGTH; i++) {
char charFromWord = word.charAt(i);
char charFromNewWord = newWord.charAt(i);
//Increment the counter if the chars are different in the same position
if(charFromWord != charFromNewWord) {
charCounter++;
}
}
return charCounter;
}
/**
* Print the result
*/
private void print() {
int i = 1;
for(String word : words) {
System.out.println("(" + i + ") : " + word);
i++;
}
}
/**
* Main method
* @param args
*/
public static void main(String[] args) {
char[] validChars = {'A','C','G','T'};
SecondTrial permutation = new SecondTrial();
permutation.combine(validChars);
permutation.print();
}
Você pegou esse código de qual site?
A parte de permutacao eu achei no site da devmedia que sao as funcoes “combine”. Ai eu adaptei pra minha necessidade adicionando a funcao addToList.
O restante eu fiz sozinho.
The closest I got from solve this issue was using Math.Random.
The problem here is that everything depends on which words are created.
Depending on a specific set of words, it is impossible to generate 96 valid ones.