Как проверить, сделаны ли еще слова из тех же символов в C?

Question

У меня следующая проблема: мне нужно вводить слова до EOF и после, чтобы сгруппировать слова, которые состоят из одинаковых символов (необязательно из одинакового количества символов).

Например:

Ввод:

"abc" "acb" "abcabc" "cab" "de" "gh" "ab" "ed" "hg" "abcde"

Выход:

"abc" "acb" "abcabc" "cab"
"de" "ed"
"gh" "hg"

Я опишу то, что я сделал до сих пор:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char **groups, word[30], **store, n = 0, k = 0;
    store = malloc(1*sizeof(char *));
    if (store == NULL) exit(1);
    for (;;) {
        printf("Enter word: ");
        if (scanf("%s", word) == EOF) break;
        store[n] = malloc((strlen(word)+1)*sizeof(char));
        if (store[n] == NULL) exit(1);
        strcpy(store[n], word);
        n++;
        store = realloc(store, (n+1)*sizeof(char *));
        if (store == NULL) exit(1);
    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    return 0;
}

Проблема в том, что я не знаю, как проверить символы. Вы можете мне помочь?

UPDATE

Я пытался сделать так, как предложил @jarmod:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char **groups, word[30], **store, n = 0, k = 0, *aux;
    store = malloc(1*sizeof(char *));
    if (store == NULL) exit(1);
    for (;;) {
        printf("Enter word: ");
        if (scanf("%s", word) == EOF) break;
        store[n] = malloc((strlen(word)+1)*sizeof(char));
        if (store[n] == NULL) exit(1);
        strcpy(store[n], word);
        n++;
        store = realloc(store, (n+1)*sizeof(char *));
        if (store == NULL) exit(1);
    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        for (int j=0; j<strlen(store[i])-1; j++) {
            for (int l=(j+1); l<strlen(store[i]); l++) {
                if (store[i][j] > store[i][l]) {
                    aux = store[i][j];
                    store[i][j] = store[i][l];
                    store[i][l] = aux;
                }
            }
        }
    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        for (int j=0; j<strlen(store[i])-1; j++) {
                if (store[i][j] == store[i][j+1]) {
                    for (int l=j; l<strlen(store[i])-1; l++) {
                        store[i][l] = store[i][l+1];
                    }
                    j--;
                    store[i] = realloc(store[i], (strlen(store[i])-1)*sizeof(char));
                    if (store[i] == NULL) exit(1);
                }
        }

    }
    for (int i=0; i<n; i++) {
        printf("%s ", store[i]);
    }
    printf("\n");
    return 0;
}

Answer 1

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

Я сделал реализацию, но фактическая часть группировки и отображения не оптимизирована. Я решаю твою проблему жестко

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int     main() {
  int       matched = 0;
  int       n_words = 0;
  char**    words = NULL;
  int*      masks = NULL;
  int       max_mask = 0;

  while (1) { // Read until EOF breaks
      char word[30];
      if (scanf("%s\n", word) == EOF)
        break;
      words = realloc(words, sizeof(char *) * (n_words + 1));
      words[n_words] = strndup(word, 30);
      n_words++;
  }

  // Computes a bit mask for each word
  masks = malloc(sizeof(int) * n_words);
  for (int i = 0; i < n_words; ++i) {
    masks[i] = 0;    
    for (int j = 0; words[i][j] != '\0'; ++j) {
      int bit_index = words[i][j] - 'a';
      masks[i] |= (1 << bit_index);
    }
    if (masks[i] > max_mask)
      max_mask = masks[i];
  }

  // Iterate over each possible masks and print all words with this mask
  for(int i = 0; i <= max_mask; i++) {
    for (int w = 0; w < n_words; w++) {
      if (masks[w] == i) {
        printf("%s ", words[w]);
        matched = 1;
      }
    }
    if (matched) {
      printf("\n");
      matched = 0;
    }
  }
  return 0;
}

Answer 2

Существует умный способ определить, к какой группе принадлежит слово.

Мы должны создать схему, в которой каждая группа однозначно идентифицируется номером. Как мы определяем и дифференцируем группу: по каким буквам она содержится. Повторяющиеся буквы не учитываются (это набор). Таким образом, нам нужна формула для кодирования набора букв группы. Если мы присваиваем каждой букве число (начиная с 0), мы получаем идентификатор с помощью суммы степеней двух (на самом деле можно выбрать любое основание, но 2 является естественным выбором для вычислений).

например:.

"abdeae" Набор букв {'a', 'b', 'd', 'e'}. Их соответствующие номера: {0, 1, 3, 4} и идентификатор 2^0 + 2^1 + 2^3 + 2^4.

Поскольку существует 26 букв, мы можем использовать 32-битное целое число для кодирования идентификатора. 2^i соответствует биту i, поэтому алгоритм выглядит так:

uint32_t letter_mask(char ch)
{
    assert(ch >= 'a' && ch <= 'z');

    return (uint32_t) 1u << (ch - 'a');
}

uint32_t word_group_id(const char * str)
{
    size_t len = strlen(str);

    uint32_t id = 0;

    for (size_t i = 0; i < len; ++i)
    {
        id |= letter_mask(str[i]);
    }

    return id;
}

---

Теперь, когда у нас есть простой способ определить группу слова, вам нужно создать упрощенную версию карты, куда поместить слова.

Это моя простая быстрая реализация. Отказ от ответственности: не проверено. Вы также должны улучшить его, добавив проверки для malloc и realloc.

typedef struct Word_map_bucket
{
    uint32_t id;
    char** words;
    size_t words_size;
} Word_map_bucket;

void init_word_map_bucket(Word_map_bucket* bucket, uint32_t id)
{
    bucket->id = id;
    bucket->words = NULL;
    bucket->words_size = 0;
}

typedef struct Word_map
{
    Word_map_bucket* buckets;
    size_t buckets_size;
} Word_map;

void init_word_map(Word_map* map)
{
    map->buckets = NULL;
    map->buckets_size = 0;
}

Word_map_bucket* find_bucket(Word_map map, uint32_t id)
{
    for (size_t i = 0; i < map.buckets_size; ++i)
    {
        if (map.buckets[i].id == id)
            return &map.buckets[i];
    }
    return NULL;
}


Word_map_bucket* add_new_bucket(Word_map* map, uint32_t id)
{
    map->buckets = realloc(map->buckets, map->buckets_size + 1);
    map->buckets_size += 1;

    Word_map_bucket* bucket = &map->buckets[map->buckets_size + 1];
    init_word_map_bucket(bucket, id);

    return bucket;
}

void add_word(Word_map* map, const char* word)
{
    // get to bucket
    uint32_t id = word_group_id(word);
    Word_map_bucket* bucket = find_bucket(*map, id);
    if (bucket == NULL)
        bucket = add_new_bucket(map, id);

    // increase bucket->words
    bucket->words = realloc(bucket->words, bucket->words_size + 1);
    bucket->words_size += 1;

    // push word into bucket
    bucket->words[bucket->words_size - 1] = malloc(strlen(word));
    strcpy(bucket->words[bucket->words_size - 1], word);
}

Answer 3

1. использовать int count[256] получить каждый символ в слове для каждого слова, например, для "abcabc", сделать count['a'] = 1 count['b'] = 1 count['c'] = 1
2. qsort со специальным сравнительным использованием count
3. вывод, для каждого слова, если count совпадает ， вывод в строку, если не выводится следующая строка

Может работать следующее code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
  unsigned char* st;
  int count[256];
};

int compare(const void* x, const void* y) {
  const struct Node* node_x = (const struct Node*)x;
  const struct Node* node_y = (const struct Node*)y;

  for (int i = 0; i != 256; ++i) {
    if (node_x->count[i] > node_y->count[i])
      return -1;
    if (node_x->count[i] < node_y->count[i])
      return 1;
  }
  return 0;
}

int main() {
  unsigned char f[][10] = {"abc", "acb", "abcabc", "cab", "de", "gh", "ab", "ed", "hg"};
  int n = sizeof(f) / sizeof(f[0]);
  struct Node node[100];

  for (int i = 0; i != n; ++i) {
    node[i].st = f[i];
    for (int j = 0; j != sizeof(node[i].count) / sizeof(node[i].count[0]); ++j)
      node[i].count[j] = 0;
    for (int j = 0; f[i][j] != '\0'; ++j) {
      unsigned char ch = f[i][j];
      node[i].count[ch] = 1;
    }
  }

  qsort(node, n, sizeof(struct Node), compare);

  int t = 0;
  for (int i = 0; i < n; ++i) {
    if (i == 0) {
      ++t;
      continue;
    }
    int k = i - 1;
    if (memcmp(node[i].count, node[k].count, sizeof(node[i].count)) == 0) {
      if (t == 1)
        printf("%s ", node[k].st);
      printf("%s ", node[i].st);
      ++t;
    } else {
      if (t != 0)
        printf("\n");
      t = 0;
    }
  }
  printf("\n");

  return 0;
}