Tạo một chuỗi ngẫu nhiên không trùng lặp trong lập trình C#

[vinhson]

mình đang có một bài tập cuối kỳ trong đó có một phần mình làm vẫn không được tốt lắm mong các bạn chỉ giúp nhé :

tạo một mảng (n phần tử biết trước) chuỗi ngẫu nhiên 6 ký tự không trùng lắp với các chuỗi trước đó

ý tưởng củ mình là

//tạo mới một mảng các ký tự sẽ được chứa trong chuỗichar[] MangKyTu = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','V','W','Y','Z','0','1','2','3','4','5','6','7','8','9'}; //tạo một chuỗi ngẫu nhiênRandom fr = new Random();            string chuoi="";            for (int i = 0; i < 6; i++)            {                int t = fr.Next(0, MangKyTu.Length);                chuoi = chuoi + MangKyTu[t];            }

sau đó tiến hành dò tìm xem chuỗi tìm được có trùng với các phần tử trước đó không, nếu trùng thì tiến hành tạo ngẫu nhiên lại, nếu không trùng thì cập nhật vô mảng


các này của minh thử với số phần tử cần tìm nhỏ thì được, lên đến cỡ 100.000 thì chậm kinh khủng

ai có các nào hay chỉ giúp mình với
cần gấp lắm

[NT_OnlyLove]

Dùng sigle linklist đi, được đó.

[vinhson]

Dùng sigle linklist đi, được đó.

bạn có thể nói rõ hơn được không vậy. Thanks

thầy mình đòi tối đa 1 triệu phần tử cơ (mới có 100.000 mà đã chậm rồi, lên đến 1triệu chắc đợi cả buổi)

[NT_OnlyLove]

Đề bài của bạn ý như thế này phải không?

1. Ví dụ các chuối sau:
abcdef
aaffes
mmsas
.......
2. Đó là các chuỗi gồm 6 ký tự không trùng lặp nhau ?
3. Vậy mình coi mỗi chuỗi đó là một Node của linklist
4. Tiến hành các thao tác sử lý so sánh và các thao tác với linklist

Mình chỉ gợi ý được vậy thui, sắp phải làm bài tập lớn rùi. Có gì không hiểu trao đổi sau.

[nhc1987]

nhc chỉ có một lời khuyên là sử dụng StringBuilder thay cho String. Điều này sẽ cải thiện đáng kể performance.

[pmtuan]

Hãy suy nghĩ thuật toán mới đi, cách làm hiện nay của bạn sẽ cực kỳ tốn kém vì độ phức tạp lên tới O(n*n).
Một cách làm với độ phức tạp O(n) là:

Thay vì phát sinh ra n chuổi 6 ký tự ngẫu nhiên, hãy phát sinh ra n số nguyên ngẫu nhiên, rồi ánh xạ mỗi số nguyên đó ra thành một chuổi 6 ký tự(ánh xạ này phải là ánh xạ một-một). Để n số nguyên phát sinh ra không được trùng nhau, ta có thể làm như sau:
+ gọi N1 là số nguyên ngẫu nhiên đầu tiên
+ N2 = N1 + một số ngẫu nhiên nhỏ nào đó
+ ...
+ Nn = N(n-1) + một số ngẫu nhiên nhỏ nào đó

Sau khi xây dựng được ánh xạ một - một đó bạn sẽ thấy được khoảng giá trị của các số nguyên cần phát sinh ngẫu nhiên.

Ai có cách làm khác thì bàn cho vui nha...

[Xcross87]

Viết một bản nháp đơn giản

   class RandomGenerator    {        public const int DEFAULT_CAPACITY = 6;        private string[] _store;        private Random _rdmizer;        private int _capacity;        private static int _current = 0;         /*         * PROPERTIES         */        public int Capacity        {            get { return _capacity; }            set { this._capacity = value; }        }         public int Current        {            get { return _current; }        }         /*         * CONSTRUCTOR         */        public RandomGenerator()        {            _store = new string[100];            for (int cnt = 0; cnt < 100; cnt++)                _store[cnt] = "";            _rdmizer = new Random();            _capacity = DEFAULT_CAPACITY;        }         /*         * METHODS         */         // Just only use to generate a random string        public string Generate()        {            StringBuilder builder = new StringBuilder();            while (builder.Length < _capacity)            {                builder.Append(_GenerateChar());            }            return builder.ToString();        }         // Add a string to store        public void Add(string _in_str)        {            _store[_current++] = _in_str;        }        // Generate the next string to the store        public string Next()        {            string _str = Generate();            if (IsStored(_str) == true)                Next();            Add(_str);                        return _str;                    }        // check whether a string stored already        public bool IsStored(string _in_str)        {            for (int _cnt = 0; _cnt < _store.Length; _cnt++)            {                if (_store[_cnt].CompareTo(_in_str) == 0)                    return true;            }            return false;        }        // get all stored strings        public string[] GetStore()        {            return _store;        }        // generate a random character        private char _GenerateChar()        {            int _num;            do             {                _num = _rdmizer.Next(48,122);            } while ((_num < 48) || (_num > 57 && _num < 65) || (_num > 90 && _num < 97));                        char chr = Convert.ToChar(_num);                        return chr;        }            }

Rồi test thử:

class Program    {        static void Main(string[] args)        {            RandomGenerator generator = new RandomGenerator();            string start = generator.Generate();            Console.WriteLine("Start: " + start);            for (int cnt = 0; cnt < 10; cnt++)                generator.Next();            string[] store = generator.GetStore();            for (int cnt = 0; cnt < store.Length && store[cnt] != ""; cnt++)                Console.WriteLine("Store: " + store[cnt]);        }    }

Kết quả:

Start: deXVjh
Store: N2je8S
Store: qlfGf3
Store: V88JZH
Store: IfjVcG
Store: rH6nVB
Store: qiKXqP
Store: KCl7TJ
Store: wQ1Co0
Store: OfsVxW
Store: POCvSk
Press any key to continue . . .

Bài tớ viết có chú thích rồi, các bạn đọc là hiểu. Đây là phương pháp trâu đầm, cứ thế mà cày code

+ Tạo một store chứa danh sách các chuỗi
+ Tạo hàm chế random chuỗi
+ Kiểm tra chuỗi đó có tồn tại trong danh sách chưa?
+ Chưa có thì thêm vào, ngược lại thì lại chế random chuỗi tiếp.

[nhc1987]

Không biết Pete có chạy thử với 1 triệu chưa ? Đo thởi gian chạy xem thế nào ?

[Xcross87]

Không biết Pete có chạy thử với 1 triệu chưa ? Đo thởi gian chạy xem thế nào ?

Amount: 10000
Execution Time: 20994 mili seconds
Press any key to continue . . .

Trâu đầm thì thế này được roài.
Với lại cái bài này tính nhiều chuỗi random làm cái gì, phi thực tế, tớ chả quan tâm.
Các bác siêu thuật toán cứ nghĩ tìm ra cách giải đi, rồi tớ xài
Nghĩ làm chi cho mệt

[vinhson]

Viết một bản nháp đơn giản
[code=CSharp]

Bài tớ viết có chú thích rồi, các bạn đọc là hiểu. Đây là phương pháp trâu đầm, cứ thế mà cày code

+ Tạo một store chứa danh sách các chuỗi
+ Tạo hàm chế random chuỗi
+ Kiểm tra chuỗi đó có tồn tại trong danh sách chưa?
+ Chưa có thì thêm vào, ngược lại thì lại chế random chuỗi tiếp.

cách này thử với 1 triệu phần tử chậm cực kỳ luôn (chắc chỉ nhanh hơn cách của mình lúc đầu)

- Bài này đúng là phi thực tế thiệt . nhưng nó áp dụng để test mảng băm trong bài tập lớn mình đang phải làm : cho người dùng nhập N chuổi vào mảng băm (chương trình sẽ tự random ra N chuỗi, chứ nếu để người dùng nhập 1 triệu chuỗi vào đó chắc chết )