Один из возможных способов, который я могу придумать, хотя, возможно, не самый эффективный:
Я собираюсь использовать ваш пример, чтобы объяснить:
A B D
A B C
A C D
создайте массив уникальных символов, чтобы вы получили (например):
A B D C
Также у вас, вероятно, должно быть перечисление, чтобы описать возможные отношения
enum Type
{
Unknown = 0,
Greater = 1,
Equal = 2,
Less = 3,
}
Теперь создайте квадратную матрицу, размеры которой совпадают с массивом выше, по умолчанию все равно Type.Unknown.
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Ваш массив будет служить индексом матрицы, когда вы будете выяснять порядок. Чтобы увидеть, что я имею в виду, посмотрите здесь:
A B D C
A 0 0 0 0
B 0 0 0 0
D 0 0 0 0
C 0 0 0 0
Пройдите и сделайте диагональ как Type.Equal
2 0 0 0
0 2 0 0
0 0 2 0
0 0 0 2
Теперь вам нужно заполнить матрицу, пройтись по каждому входному массиву и получить каждый символ и один после него. Используйте эти 2 символа, найдите индекс в матрице для каждого (используя ваш массив) и обновите матрицу.
for(int i=0; i<len(arr)-1; i++)
{
char c1 = arr[i], c2 = arr[i+1];
int i1,i2;
//get indices of characters in array and put in i1, and i2 respectively
matrix[i1][i2] = Type.Less;
matrix[i2][i1] = Type.Greater
}
Вы назначаете 2 места в сетке каждый раз, потому что когда один символ меньше другого, это также означает, что второй символ больше первого.
Теперь вы просто вставляете символы в массив по одному (Linked List будет самым простым, вы поймете почему через секунду)
Каждый раз, когда вы вставляете символ, вы начинаете с начала вашего возвращаемого массива и выполняете итерацию, просматривая индексы в первом массиве и проверяя матрицу для Type.Greater или Type.Less (Зависит от по какому пути вы сравниваете, переводите char в массив или array to current char) и вставляете его, если встречаете значение, отличное от ожидаемого.
Если вы нажали Type.Unknown в matix во время вставки, вы знаете, что у вас недостаточно информации для сортировки этих массивов, если вы нажали Type.Equal, вы можете игнорировать вставку этого символа (если вы не Я не хочу дубликатов в вашем результате.)
И тогда вы выведете свой возвращаемый массив