Algorithm - can set of strings be represented as composition of two sets?

Here's an algorithm:

Alphabet: {a,b,c}

Strings: aba ca abb cb

The most complete solution to this is to build a dictionary M, mapping each string onto the letters, that existed in {a,b,c}, which have been occurred once or multiple times. Here, it's not necessary to set the mappings of the duplicate letters, so that the dictionary M will be a rectangular matrix 4 x 3, consisting of the following elements:

a b c

aba : 1, 1, 0
ca : 1, 0, 1
abb : 1, 1, 0
cb : 0, 1, 1


For instance, the string "abb" contains 1 - 'a' and 2 - 'b', such as that the row of matrix M is { 1, 1, 0 }, for which 1 and 1 values are corresponding to letters 'a' and 'b', respectively, and 0 corresponds to the letter 'c', which has not been found in the string "abb".

Next, take the inner product of the matrix M and its transpose, to obtain the symmetric matrix I=MM^T of shape 4 x 4.

I=MM^T (Upper triangular):

0 1 2 0
0 0 1 0
0 0 0 0
0 0 0 0

Finally, check whether at least one element, on the I matrix's diagonal, is equal to 0. If so, the composition does not exist and the result is "FALSE", or "TRUE", unless otherwise.

Here's a code snippet, written in plain C89, illustrating the algorithm, above:

#include <vector>
#include <fstream>
#include <iostream>

int main()
{
    const char* filename = "tZwciVLk.txt";

    std::ifstream ifs(filename, \
        std::ifstream::ios_base::in);

    std::vector<std::string> strings;

    char* line = (char*)new char[256];

    while (ifs.getline(line, 256))
        strings.push_back(line);

    std::string chars = "abc";

    if (strings.size() == 1) {

        std::size_t i = 0; bool f = false;
        const char* string = \
            strings[strings.size() - 1].c_str();
        f = strcmp("\0", string) == 0;
        while (i < strlen(string) && !f)
            f = strchr(chars.data(), string[i++]);

        printf("Output: %s\n", f ? "True" : "False");

        return 0;
    }

    int** M = (int**)malloc(strings.size() * sizeof(int*));
    int** I = (int**)malloc(strings.size() * sizeof(int*));

    std::size_t n = 0;
    for (std::size_t i = 0; i < strings.size(); i++) {
        M[i] = (int*)malloc(chars.size() * sizeof(int));
        const char* s = strings[i].data();
        if (strcmp("\0", s) < 0) {
            for (std::size_t j = 0; j < chars.size(); j++)
                M[n][j] = strchr(s, chars[j]) ? 1 : 0;

            n++;
        }
    }

    bool f = true;
    for (std::size_t i = 0; i < n && f; i++) {
        I[i] = (int*)malloc(strings.size() * sizeof(int));
        memset((void*)I[i], 0x00, strings.size() * sizeof(int));
        for (std::size_t j = 0; j < n && f; j++) {
            for (std::size_t k = 0; k < chars.size(); k++)
                I[i][j] += M[i][k] * M[j][k];

        }

        f = I[i][i] == 0 ? 0 : 1;
    }

    for (std::size_t i = 0; i < n; i++)
         std::cout << strings[i] << " ";

    std::cout << std::endl;

    std::cout << "Output: " << (f == true ? "True" : "False") << std::endl;

    return 0;
}

Outputs:

Alphabet: {a,b,c}
Strings: aba ca abb cb
Output: True

Alphabet: {a,b,c}
Strings: aba ca abb cb d
Output: False

Alphabet: {a,b,c}
Strings: tt yyyy zz dd ppp
Output: False

Alphabet: {a,b,c}
Strings: tt yyyy zz dd ppp
Output: False

Alphabet: {a,b,c}
Strings: xp
Output: False

Alphabet: {a,b,c}
Strings: ax
Output: True

Edit:

Also, this is implementation-specific. You can also find an intersection of the alphabet and each string to do that, something like:

using System.Linq;

char[] chars = {'a','b','c'};
String[] strings = { "aba", "ca", "abb", "cb", "zz" };

bool isComposition(String[] strings, char[] chars) {
    return strings.Select(s => s.Intersect(chars).Any()).ToArray().All(s => s);
}

Console.WriteLine(isComposition(strings, chars));

Good Luck! :)