Kombinationen sortieren

Hallo,

ich habe ein Problem: Und zwar handelt es sich um Aminosäurepeptidepermutationen. Ist aber komplett unwichtig was genau das ist weil da ein einfaches System hintersteckt. Also hier die Erklärung: Jedes Peptid besteht aus verschiedenen Aminosäuren von denen es 20 wichtige gibt. Jede dieser 20 Aminosäuren erhält nun einen Buchstaben (A, B, C ...) und demnach werden Peptide dann durch Buchstabenkombinationen dargestellt (z.B. CAB, BAC, ABC...). Was ich nun machen will ist folgendes: Zunächst sollen alle möglichen Peptide erzeugt werden und dann sollen sie sortiert werden. Hier ein kleines Beispiel:
Wenn man ein Peptid mit zwei Aminosäuren nimmt und zur Veranschaulichung hier nur 4 verschiedene Aminosäuren nimmt, ergibt sich folgenes Bild: AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD
Dies kann man sich besonders gut durch eine Matrix verdeutlichen:
-A- -B- -C- -D-

-A- AA AB AC AD

-B- BA BB BC BD

-C- CA CB CC CD

-D- DA DB DC DD

Nunja, jetzt sollen diese Polypeptide sortiert werden, was am Ende so aussehen soll: Eine Gruppe mit den gleichen Buchstaben und eine mit den unterschiedlichen, also so: AA, BB, CC, DD und die andere Gruppe: AB, AC,AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.

Programmiertechnisch habe ich das folgendermaßen gelöst:
Zunächst einmal wird mit Zahlen gerechnet, deswegen wird jeder Aminosäure eine Zahl zugeordnet (0-19):
Dies führte zu der Funktion "Trans", die einen String, also den passenden Buchstaben ausgibt, um ihn zu langen Ketten zusammenzufügen und anzuzeigen (z.B. in einer ListBox):
String __fastcall TForm1::Trans (int Number)
{
switch (Number)
{
case 0:
return "A";
case 1:
return "C";
case 2:
return "D";
case 3:
return "E";
case 4:
return "F";
case 5:
return "G";
case 6:
return "H";
case 7:
return "I";
case 8:
return "K";
case 9:
return "L";
case 10:
return "M";
case 11:
return "N";
case 12:
return "P";
case 13:
return "Q";
case 14:
return "R";
case 15:
return "S";
case 16:
return "T";
case 17:
return "V";
case 18:
return "W";
case 19:
return "Y";
}
}

So der eigentliche Kreierungs- und Aussortierungsprozess kommt jetzt:
void __fastcall TForm1::CreateTwo(void)
{
for (int a=0;a<n;a++)
{
for (int b=0;b<n;b++)
{
if (a==b) // AA
{
AA->Items->Add(Trans(a) + Trans(b));
}
if (a!=b) // AB
{
AB->Items->Add(Trans(a) + Trans(b));
}
ProgressBar1->Position++;
}
}
}

Hier werden also zwei Schleifen gestartet. Vorzustellen wie so einfache Zahlenschlösser: Man dreht immer einen weiter und wenn man bei einer bestimmten Zahl angekommen ist, dreht man das nächste eins höher und wiederholt das Spielchen. Dadurch entstehen Zahlen Kombinationen die in Buchstabenkombinationen umgewandelt werden (Trans) und dann einer ListBox (AA, für alle gleichen, und AB, für alle ungleichen) hinzugefügt werden. Die Filterung liegt hierbei bei der if-Bedingung.
Nunja das war der Prozess für einen sogenannten 2-mer. Jedoch soll das bis hoch zu 20 oder gar 30-mer gehen, also eine unvorstellbar große Anzahl an Kombinationen. Diese Anzahl kann theoretisch recht einfach erzeigt werden, indem man einfach die Schleifen weiter ineinander verschachtelt. Das Problem liegt hier nur bei der Sortierung in Gruppen.
Hier nochmal das Beispiel für einen 3-mer
void __fastcall TForm1::CreateThree(void)
{
for (int a=0;a<n;a++)
{
for (int b=0;b<n;b++)
{
for (int c=0; c<n; c++)
{
if ((a==b)&&(a==c)) // AAA
{
AAA->Items->Add(Trans(a) + Trans(b) + Trans(c));
}
else if (a==b) // AAB
{
AAB->Items->Add(Trans(a) + Trans(b) + Trans(c));
}
else if (a==c) // ABA
{
ABA->Items->Add(Trans(a) + Trans(b) + Trans(c));
}
else if (b==c) // BAA
{
ABB->Items->Add(Trans(a) + Trans(b) + Trans(c));
}
else // ABC
{
ABC->Items->Add(Trans(a) + Trans(b) + Trans(c));
}
}
ProgressBar1->Position++;
}
}
}

Wie man sieht, ist die Anzahl an Gruppen schon recht größer geworden.
Hier für einen 4-mer:
void __fastcall TForm1::CreateFour(void)
{
for (int a=0;a<n;a++)
{
for (int b=0;b<n;b++)
{
for (int c=0; c<n; c++)
{
for (int d=0; d<n; d++)
{
if ((a==b)&&(a==c)&&(a==d)) // AAAA
{
AAAA->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
// ------
else if ((a==b)&&(a==c)) // AAAB
{
AAAB->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if ((a==b)&&(a==d)) // AABA
{
AABA->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if ((a==c)&&(a==d)) // ABAA
{
ABAA->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if ((b==c)&&(b==d)) // ABBB
{
ABBB->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
// ------
else if ((a==b)&&(c==d)) // AABB
{
AABB->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if ((a==c)&&(b==d)) // ABAB
{
ABAB->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if ((a==d)&&(b==c)) // ABBA
{
ABBA->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
// ------
else if (a==b) // AABC
{
AABC->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if (a==c) // ABAC
{
ABAC->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if (a==d) // ABCA
{
ABCA->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if (b==c) // ABBC
{
ABBC->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if (b==d) // ABCB
{
ABCB->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
else if (c==d) // ABCC
{
ABCC->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
// ------
else // ABCD
{
ABCD->Items->Add(Trans(a) + Trans(b) + Trans(c) + Trans(d));
}
}
}
ProgressBar1->Position++;
}
}
}

Wie man sieht steigt die Anzahl an möglichen Gruppen nicht linear sondern explodiert quasi. Leider kann ich dahinter kein System entdecken. Und hier ist genau mein Problem. Weiß jemand vielleicht wie man die Gruppen vorraussagen kann oder die Gruppen erstellen kann?
Ich hab einen Screenshot angefügt, leider erlauben die Bestimmungen von PC-Welt nur eine Breite von 320 Pixeln, deswegen ist das Bild sehr schlecht zu erkennen. Nunja, ich hoffe ihr könnt mir helfen. Bei Fragen steh ich gerne zur Verfügung.

Ich benutzte den C++ Builder 6 Personal.

Danke schonmal im Vorraus und Guten Rutsch
>XS<

 

Da die Leerzeichen entfernt wurden, lade ich hier den Post nochmal im TXT-Format hoch. Somit ist er leicht zu lesen und demnach auch verständlicher. Danke.

 

Hallo Hascheff,

Entschuldigung, aber mir leuchtet eher dein Sortiersystem nicht ein: Die Reihenfolge die du dahin geschrieben hast, ist ja genau die, die der Computer durch die Schleifen berechnet, da ist ja überhaupt nichts sortiert. Meine Idee war die einzelnen Kombinationen in nach Ähnlichkeiten erstellten Gruppen zu sortieren. Denn du musst mir zustimmen, dass AAB und AAC sich einander ähnlich sind, genauso wie AAA und BBB oder BCB und ACA. Und der ganze Grund für diese Mühe ist folgender: Nein, ich bin kein Informatik-Schüler, ich belege sogar noch nicht einmal Informatik. Meine Grundkenntnisse von C++ habe ich aus einem Buch und den Rest habe ich mir selber beigebracht bzw. dazu gelernt. Jedenfalls habe ich dieses Programm für einen Freund geschrieben, der als freiberuflicher Wissenschaftler tätig ist. Ich versteh zwar nicht zu 100 % was er damit machen will, aber verstehe schon, wie er es gern hätte. Und diese ganzen Kombinationen sollen in Gruppen sortiert werden, um z.B. gucken zu können, aha, was für Mutationen sind nahe liegend, wenn man diese oder jene Aminosäurepermutation vorliegen hat. Es soll also quasi als Erkennungssystem dienen. Nunja, ein anderer Freund hatte mir vorgeschlagen doch einfach ein Array zu nehmen, und dann die einzelnen Buchstaben durchzugehen und nach der Anzahl von gleichen Buchstaben zu sortieren. Das Problem wäre hier nur, dass z.B. ABAB in der gleichen Gruppe wie AABB wäre, weil eben in beiden zwei mal A und zwei mal B vorkommen. Diese Sortiermethode scheidet also schon mal aus. Als einzige Methode, die wirklich funktioniert, scheint mir meine im Moment, da sie wirklich jede mögliche Gruppe durch eine if-Bedingung bestimmt, das Problem ist halt, wie gesagt, nur, dass sich kein System entdecken lässt und man sich wirklich überlegen muss welche Gruppe kann es geben und da können auch leicht mal ein paar Gruppen übersehen werden.
Ich hoffe ich konnte deine Frage klären. Was ich also bräuchte wäre ein neues effektives Sortiersystem oder eine Methode zur Erzeugung der Gruppen, in die die Werte einsortiert werden können.

Vielen Dank schon einmal, dass du dich mit dem Problem beschäftigen willst. Bist du denn ein Programmierer oder wie?

Gruß,
>XS<

 

in c++ gibts Schleifen, nutze sie!

Was ich mitbekommen habe willst du einfach ein 2D Array sortieren, mit der außnahme das du wenn alle chars in einer Reihe gleich sind, sie extra ausgeben willst... hab ich das richtig verstanden?

Das mit den selben Buchstaben extra ausgeben hab ich im moment keine Lust mehr musst alleine machen. Ich hoffe ich habs richtig verstanden was du willst ....

Code mit 256 Aminosäuren und 10 Zeichen Peptid mal 10, was auch immer das ist. Du kannst den Code beliebig erweitern.


int temp[10][1];
int arry[10][10];
char carry[10][10]={
{'a','a','b','a','b','a','b'}
,{'a','a','b','b','a','b','f'}
,{'a','a','b'}
,{'z','s','f'}
,{'b','s','f','b','s','f','s'}
,{'a','s','f'}
,{'a','a','b'}
,{'a','a','z'}
,{'a','a','b'}
,{'a','s','f'}};

// char to int
for(int l=0;l<10;l++){
for(int i=0;i<10;i++){
if( carry[l]==0){
arry[l] = 0;
}else{
arry[l] = static_cast<int>(carry[l]);
}}}

//sort chars
for(int l=0;l<10;l++){
for(int i=0; i<10;i++){
for(int m=i+1;m<10;m++){
if(arry[l][m]<arry[l]){
int z = arry[l][m];
arry[l][m] = arry[l];
arry[l] = z;
}
}
}
}

//sort rows
for(int l=9;l>=0;l--){
for(int i=0; i<10;i++){
for(int m=i+1;m<10;m++){
if(arry[m][l]<arry[l]){
for(int k=0;k<10;k++){
temp[m][k] = arry[m][k];
arry[m][k] = arry[k];
arry[k] = temp[m][k];
}
}
}
}
}


// out
for(int l =0;l<10;l++){
for(int i =0;i<10;i++){
carry[l] = static_cast<char>(arry[l]);
cout << carry[l];
}
cout << "\n";
}
cin.get();

 

Ich glaube, es geht genau darum.

Also keine stupide 2D-Sortierei sondern eher xD (und damit ist jetzt nicht das lachende, augenzusammenkneifende Smiley gemeint ).

Ich hab's so verstanden, dass der TO nich weiß, wie er for-Schleifen quasi beliebig ineinander verschachteln kann, oder?

Ich hatte mal ein ähnliches Problem, glaub ich, vielleicht finde ich ja noch nen Quellcodefetzen davon...

 

@daboom: Nein, soweit ich verstanden habe ist nicht die Erzeugung sondern die Sortierung das Problem. Ansonsten wäre das ganze ja über Rekursion kein Problem.

@x-shadow-x: Mir persönlich ist noch nicht klar, wie genau du deine Kombinationen sortieren willst und warum? sind sich AAA und BBB biologisch gesehen wirklich ähnlicher als AAA und AAB?

Außerdem ist die Frage, wie "genau" du deine Kombinationen sortiert haben willst. Schließlich haben zwei 30-stellige Kombinationen viel schneller eine Ähnlichkeit als zwei 3-stellige.
z.B. gibt es imho keine Sinn AXXXAXXXXXXXX..... und AXXXAXXXXXXXX...
(X= beliebige verschiedene Buchstaben) in die gleiche Gruppe zu tun, nur weil bei beiden 1. und 5. Stelle gleich sind.

Ein bisschen mehr Informationen über den Hintergrund und die Verwendung der sortierten Ausgabe wäre daher nützlich.