Chcem vytvoriť celý rad všetkých permutáciíséria 4 písmen (volať ich A, C, G, T pre 4 typy nukleotidových báz). Program by mal požiadať užívateľa o hodnotu k, dĺžku permutácie. Mám to fungujúce do tej miery, že dokážem získať permutácie, ale zobrazuje len tie bez opakovania. Tu je program, výstup, ktorý mi teraz dáva, a výstup, ktorý chcem dať. ja.
import java.util.Arrays;
import TerminalIO.*;
public class Permute {
static KeyboardReader reader= new KeyboardReader ();
static int k= reader.readInt("Enter k-tuple");
static void permute(int level, String permuted,
boolean[] used, String original) {
if (level == k) {
System.out.println(permuted);
} else {
for (int i = 0; i < 4; i++) {
if (!used[i]) {
used[i] = true;
permute(level + 1, permuted + original.charAt(i), used, original);
used[i] = false;
}
}
}
}
public static void main(String[] args) {
String s = "ACGTACGTACGTACGTACGT";
boolean used[] = new boolean[20];
Arrays.fill(used, false);
permute(0, "", used, s);
}
}
Keď zadám hodnotu K 2, dáva mi to:
- AC
- AG
- AT
- CA
- CG
- CT
- GA
- GC
- GT
- TA
- TC
- TG
V ideálnom prípade by tlačila:
- AC
- AG
- AT
- AA
- CA
- CC
- CG
- CT
- GA
- GG
- GC
- GT
- TA
- TC
- TG
- TT
odpovede:
1 pre odpoveď č. 1public class Permute {
static String s = "ACGT";
static void permute(int level, String prefix) {
if (level == 0) {
System.out.println(prefix);
return;
}
for (int i = 0; i < s.length(); i++)
permute(level - 1, prefix + s.charAt(i));
}
public static void main(String[] args) {
int k = 4;
permute(k, "");
}
}
1 pre odpoveď č. 2
A čo toto? (bez rekurzie)
void permute(char[] alphabet, int k) {
int permutationNumber = (int) Math.pow(alphabet.length, k);
for (int i = 0; i < permutationNumber; i++) {
for (int j = 0; j < k; j++) {
System.out.print(alphabet[(i + (j * i / alphabet.length)) % alphabet.length]);
}
System.out.println();
}
}
1 pre odpoveď č. 3
ArrayList<ArrayList<String>> results= new ArrayList<ArrayList<String>>();
public static void main(String... args) {
String[] letters= new String[] {"a", "t", "g", "c"};
List<String> list= Arrays.asList(letters);
for (int i=0; i<list.size(); i++) {
ArrayList<String> startList= new ArrayList<String>();
startList.add(list.get(i));
permute(list, 2, startList);
}
//result lists of strings are saved in results
for (ArrayList<String> result : results) {
System.out.println(result);
}
}
private static void permute(List<String> letters, int endLength, List<String> startList) {
if (startList.size() >= endLength) {
results.add(startList);
return;
}
for (int i=0; i<letters.size(); i++) {
ArrayList<String> newStartList= new ArrayList<String>(startList);
newStartList.add(letters.get(i));
permute(letters, 2, newStartList);
}
}