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?
/** Length of the word */privatestaticfinalintWORD_LENGTH=6;/** The words most differ in at least 3 positions */privatestaticfinalintMINIMUM_CHAR_DIFFERENCE=3;/** Newly created word */privatefinalchar[]newWord=newchar[WORD_LENGTH];/** List with the filtered items */privatefinalList<String>words=newArrayList<>();/** * Generates all possible combinations and adds it to the permutations list if the generated word is valid * @param validChars dictionary of possible chars */privatevoidcombine(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 */privatevoidcombine(char[]validChars,intposition){if(position==newWord.length){addToList(newWord);}else{for(charvalidChar:validChars){newWord[position]=validChar;combine(validChars,position+1);}}}/** * Add the word to the complete list */privatevoidaddToList(char[]newWord){Stringword=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 */privateStringcharArrayToString(char[]word){returnString.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 */privatebooleanisWordValid(StringnewWord){//Iterate the list of wordsfor(Stringword:words){intcharCounter=getNumberOfDifferentChars(word,newWord);//The counter is bigger or equal than 3, which means the word is valid.if(charCounter<=MINIMUM_CHAR_DIFFERENCE){returnfalse;}}returntrue;}/** * 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 */privateintgetNumberOfDifferentChars(Stringword,StringnewWord){intcharCounter=0;//Iterate the chars from each wordfor(inti=0;i<WORD_LENGTH;i++){charcharFromWord=word.charAt(i);charcharFromNewWord=newWord.charAt(i);//Increment the counter if the chars are different in the same positionif(charFromWord!=charFromNewWord){charCounter++;}}returncharCounter;}/** * Print the result */privatevoidprint(){inti=1;for(Stringword:words){System.out.println("("+i+") : "+word);i++;}}/** * Main method * @param args */publicstaticvoidmain(String[]args){char[]validChars={'A','C','G','T'};SecondTrialpermutation=newSecondTrial();permutation.combine(validChars);permutation.print();}
F
Fefo80
Você pegou esse código de qual site?
C
Colombo86
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.
C
Colombo86
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.