Không hiểu cách hoạt động của set<char>

#1

Chào mọi người ạ. Em đang học về thư viện chuẩn C++ phần set thì có bài tập như thế này:

Trong ngôn ngữ Aramic từ có thể đại diện cho các đối tượng.

Các từ trong Aramic có tính chất đặc biệt:

  • Một từ là một gốc nếu nó không chứa cùng một chữ cái nhiều lần.
  • Một gốc và tất cả các hoán vị của nó cũng chỉ đại diện cho cùng một đối tượng.
  • Từ gốc x của một từ y là từ chứa tất cả các chữ cái xuất hiện trong y theo cách mà mỗi chữ cái xuất hiện một lần. Ví dụ: gốc của "aaaa" , "aa" , "aaa" là "a" , gốc của "aabb" , "bab" , "baabb" , "ab" là "ab" .
  • Bất kỳ từ nào trong Aramic đại diện cho cùng một đối tượng với gốc của nó.

Bạn có một dãy từ Aramic. Hãy đưa ra số lượng đối tượng khác nhau trong dãy đó.

Ví dụ:

  • Với words = ["a","aa","aaa","ab","abb"] thì kết quả là: aramic(words) = 2.

thì có code mẫu là thế này

int aramic(std::vector<std::string> words)
{
    set<string> s;
    
    for(int i=0; i<words.size(); i++){
        string str = words[i];
        set<char> ch;
        for(int j=0; j<str.length(); j++){
            ch.insert(str[j]);
        }
        string e="";
        for(auto x:ch) e+=x;
        s.insert(e);
    }
    return s.size();
}

Em không hiểu rõ đoạn for lắm, có ai giải thích giúp em đoạn này được không ạ? Đoạn này theo em hiểu là lưu vector word vào string str, sau đó khởi tạo set<char>ch để kiểm tra, sau đó tiếp tục một vòng lặp thêm các phần tử trong str vào set chạy từ phần tử đầu tiên đến phần tử cuối của string str. Ở đây là set<char> nên em thắc mắc khi insert vào nó sẽ như thế nào, ví dụ như “bda” thì vào trong set<char> nó sẽ là ‘b’,‘d’,‘a’ hay nó vẫn là ‘bda’, hay là sẽ ra kết quả khác vì em thấy đầu ra như 2 kiểu trên đều sai sai…?

#2

set là một tập hợp, một bộ không lặp
khái niệm về tập hợp không lặp chắc cấp 3 cũng có học rồi chứ nhỉ

3 Likes
#3

Em biết là các phần tử trong set không lặp. Cái em đang hỏi là khi insert string vào set thì nó sẽ lưu thế nào?

#4

đâu cần biết người ta implement nó như nào, chỉ cần biết thêm string đó vào s có ý nghĩa gì là được rồi
còn câu hỏi kiểu như vậy thì cũng giống như hỏi “int a = 1;” hỏi gán như vậy thì làm thế nào mà nó lưu được

1 Like
#5

Em nghĩ chắc anh không hiểu ý em rồi. Em muốn biết là set nó lưu vào thế nào thì em mới hiểu và làm bài tập được. Ví dụ như “bda” thì vào trong set<char> nó sẽ là ‘b’,‘d’,‘a’ hay nó vẫn là ‘bda’ hay nó là cái gì khác? Vì set không lưu những phần tử giống nhau nên nếu nó lưu “bda” thì “adb”, “dab” gì đó gì căn bản không tìm được từ gốc. Mà nếu lưu từng phần tử như ‘b’, ‘d’, ‘a’ thì giả sử vector có “a”, “bc”, “aa”, “bcc” thì trong set chỉ có các phần tử ‘a’, ‘b’, ‘c’ ?
Với lại anh giải thích hộ em luôn đoạn dưới với, chỗ auto x:ch viết tắt em đọc khó hiểu quá :cry:

#6

mình không thấy chỗ nào lưu string thêm vào set ?

#7

Ủa cái ch.insert(str[j]) là thêm char vào char ạ? Em tưởng

string str = word[i];

là nó lưu các phần tử của std::vectorstd::string words vào string str thì ch.insert(str[j]) này là thêm string vào char? Hay là tại vì do set nên string str lưu vào set sẽ thành từng char trong string lưu vào set đúng không ạ?

Và nếu được thì anh giải thích hộ em phần này với, viết tắt em đọc khó hiểu:

for(auto x:ch) e+=x;
    s.insert(e);
}
#8

dấu ngoặc ở cuối là sao? nó là của dòng for lớn bên ngoài, bạn trích dẫn mà lại mang nó vào thì liên quan gì for

1 Like
#9 
// vd str = "baabb"
string str = words[i];
// đoạn code này chuyển string "baabb" thành set ch = {'a', 'b'}
set<char> ch;
for(int j=0; j<str.length(); j++)
  ch.insert(str[j]);
// đoạn code này chuyển set {'a', 'b'} thành chuỗi e = "ab"
string e="";
for(auto x:ch) e+=x;
// thêm e = "ab" vào set s
s.insert(e);

thật ra để chuyển string “baabb” thành set {‘a’, ‘b’} chỉ cần 1 dòng thế này :V

set<char> ch(begin(str), end(str));

và chuyển set {‘a’, ‘b’} thành chuỗi “ab” cũng chỉ cần 1 dòng :V

string e(begin(ch), end(ch));

dòng for kia vì lặp hết các từ nên có thể xài range based for loop :V

for (auto& str : words) { ... // str có kiểu là string& hoặc const string& tùy vào `words` là vector<string> hay const vector<string>

hàm aramic có thể viết lại là

set<string> s;
for (auto& str : words) {
    set<char> ch(begin(str), end(str));
    s.insert(string(begin(ch), end(ch)));
}
return s.size();

soành điệu xài STL algo thì :V :V

set<string> s;
transform(begin(words), end(words), inserter(s, end(s)), [](auto& str){
    set<char> ch(begin(str), end(str));
    return string(begin(ch), end(ch));
});
return s.size();
5 Likes
#10

Em hiểu rồi, cảm ơn anh ạ

#11

à thật ra để lấy các phần tử riêng biệt ko trùng nhau trong chuỗi có thể xài std::unique sau khi sort chuỗi đó :V, ko cần dùng set<char> ch :V

string ch = str; // vẫn phải tạo 1 biến ch, nhưng ở đây nó có kiểu là string 
sort(begin(ch), end(ch));  // sau khi sort ch = "aabbb"
auto last = unique(begin(ch), end(ch)); // sau dòng này ch = "ab###" trong đó ### là các ký tự đã bị xóa, ko chắc là ký tự gì :V 
                                        // last là iterator tới ^ là ký tự sau ký tự có nghĩa cuối cùng, ở đây là ký tự # liền sau 'b'
ch.erase(last, end(ch)); // unique() ko thực sự xóa mấy ký tự thừa đó, vì nó ko resize mảng ch được, phải cần dòng này để xóa ### đi
// có thể viết 2 dòng trên lại thành 1 dòng:
////// ch.erase(unique(begin(ch), end(ch)), end(ch));
// sau khi xóa ###, ch = "ab", sẵn sàng được insert vào s

viết tóm lại là

set<string> s;
for (auto& str : words) {
    auto ch = str;
    sort(begin(ch), end(ch)); // đừng quên sort trước khi xài unique() :V 
    ch.erase(unique(begin(ch), end(ch)), end(ch));
    s.insert(ch);
}
return s.size();

// soành điệu :V:V
set<string> s;
transform(begin(words), end(words), inserter(s, end(s)), [](auto& str){
    auto ch = str;
    sort(begin(ch), end(ch)); // đừng quên sort trước khi xài unique() :V 
    ch.erase(unique(begin(ch), end(ch)), end(ch));
    return ch;
});
return s.size();

trong vòng for (auto& ... : ...) cứ nên xài auto& hết :V muốn tạo copy thì vô trong {} mà tạo cho nó rõ ràng, for (auto ... : ...) tuy ngắn nhưng dễ bỏ qua n copy :V

xài set<char> có 2 dòng trong loop kia :V còn ở đây tới 4 dòng :V nhưng cách unique() này lẹ hơn set<char> :V

5 Likes
#12

https://en.cppreference.com/w/cpp/container/list/unique
https://en.cppreference.com/w/cpp/algorithm/unique

Removes all consecutive duplicate elements from the container

sao lại đặt tên quái thế nhỉ, người ta cứ nghĩ là nó giống [1,2,1,2,3].uniq! rồi dùng thoải mái thì toang.

4 Likes
#13

:V :V list cũng có hàm unique() riêng à
cũng như std::unique phải gọi std::sort trước thì std::list cũng phải gọi std::list::sort() trước thôi =]

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?