Как при сортировке массива строк сортировать без строк?

Question

[Сергей]

Есть массив строк
Нужно отсортировать его и взять из каждой строки последний символ

Эти строки генерируются по алгоритму: последний символ перемещается на первое место.

Я подумал что может можно как то не хранить их а просто из сгенерированной строки брать последний символ и код по которому можно будет потом отсортировать те последние символы что я взял.

код строки и её последний символ

public class Element
    {
        public char Symbol;
        public int Hash;

        public static Element Create(StringBuilder str)
        {
            int code = 0;

            //как нибудь считается этот код)
            for (int i = 0; i < str.Length; i++)
            {
                code +=(str[i] - 'a'+ 1) * (str.Length - i) + 127 *(str.Length - i);
            }


            return new Element { Symbol = str[str.Length - 1], Hash = code};
        }
    }

в цикле перестановка и вызов Element

for (int i = 0; i < strL; i++)
            {
                curStr.Insert(0, curStr[strL - 1]);
                curStr.Remove(strL, 1);
                list.Add(Element.Create(curStr));
            }

Comments

[freeExec]

Вам всё равно придётся сортировать, вам нужен параметр, на какой позиции в сортированном списке будет каждый символ в строке. В общем делаете сложности ну пустом месте.

[Сергей]

freeExec,
Нужно закодировать строку этим алгоритмом
Преобразование Барроуза — Уилера

1. На вход подаётся сама строка
   
2. Затем создаётся массив строк(количество = количеству символов строки)
   
3. Потом массив сортируется
   
4. Из каждой строки в массиве берётся последний символ
   
5. Создаётся новая строка
   

И если строка содержит 200 символов, то придётся создавать ещё 199 строк размером в 200 символов
И мне все строки не нужны потом будут, только последние символы. А в C# они ведь сохраняются где в памяти.
Вот я и хочу их не создавать.

Решил спросить может есть какой нибудь алгоритм который может посчитать вес строки.

Есть ещё вариант сделать свой класс в котором будет ссылка на первую строку и сдвиг на сколько то символов. А потом просто сравнивать строки посимвольно. И вместо строк отсортировать эти классы)

[#]

Сергей, удалил свой ответ. очевидно он что вам бесполезен. а с прочими размышлениями по теме вы ознакомились. успехов

Answer 1

[Сергей]

Вот что я сделал

private class VirtualStringBWT : IComparable<VirtualStringBWT>, IEnumerable<char>
        {
            char[] _sourse;
            int _shiftRight;

            public VirtualStringBWT(char[] sourse, int shift)
            {
                if (shift >= sourse.Length)
                    throw new ArgumentOutOfRangeException("Нельзя сдвигать на число большее или равное количеству символов!");

                _sourse = sourse;
                _shiftRight = shift;
            }

            public int CompareTo(VirtualStringBWT other)
            {
                if (other == null)
                    throw new NullReferenceException();

                IEnumerator<char> thisEnumerator = this.GetEnumerator();
                IEnumerator<char> otherEnumerator = other.GetEnumerator();

                //строки одинаковой длины
                while (thisEnumerator.MoveNext() && otherEnumerator.MoveNext())
                {
                    if (thisEnumerator.Current > otherEnumerator.Current)
                        return 1;
                    else if (thisEnumerator.Current < otherEnumerator.Current)
                        return -1;
                }

                return 0;
            }

            public IEnumerator<char> GetEnumerator()
            {
                int startI = _sourse.Length - _shiftRight;
                int i = startI;
                while (i < _sourse.Length)
                {
                    yield return _sourse[i];
                    i++;
                }

                i = 0;

                while (i < startI)
                {
                    yield return _sourse[i];
                    i++;
                }
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }
        }
    }

1) Из строки которую нужно закодировать я делаю массив символов, который будет один для всех VirtualString.
2) Затем создаю n штук VirtualString куда передаю массив символов и сдвиг.

for (int i = 0; i < _source.Length; i++)
       list.Add(new VirtualStringBWT(t, i));

3) Когда обращаюсь к объекту VirtualString он начинает выдавать массив с определённой позиции.
И я не создаю 200 строк.
Ура)