ho to implement Sets in matlab

hey everybody,, how to use Matlab in the set. problem: A = {1,2}, A ^ 2 = {(1,1), (1,2), (2,2) (2,1)};

how to find A ^ 100 by using Matlab?

[John BG]

In this question the operation A^2 means

% find all combinations with repetition.

Since A is defined containing 2 digits only, A^100 is the same as asking

% find all combinations with repetition of 100 bits

100 bits are 30 digits in binary.

John BG <mailto:[e-mail] [e-mail]>

[Walter Roberson]

Slight rephrasing there: Numbers of 100 binary digits require just over 30 decimal digits.

Answer 1

[Walter Roberson]

    P = 100;

    A = uint8([1, 2]);    %if your stored values exceed 255 then change the uint8 to suit

    lenA = length(A);
    if lenA <= intmax('uint8')
      sstype = 'uint8';
    elseif lenA <= intmax('uint16')
      sstype = 'uint16';
    elseif lenA <= intmax('uint64')
      sstype = 'uint64';
    else
      error('A is too large to be able to subscript into. How did you even manage to create it??');
    end

    num_AP = lenA^P;
    try
      AP = zeros(num_AP, P, class(A));
    catch
      whoA = whos('A');
      bytes_per_entry = whoA.bytes ./ lenA;
      A_bytes_required = num_AP * P * bytes_per_entry;
      error('You need to install more memory; you need at least %g bytes of memory', A_bytes_required);
    end

    T = zeros(1, P, sstype);

    for J = 1 : num_AP
      AP(J,:) = A(T+1);
      for K = P : -1 : 1
        if T(K) ~= lenA - 1
          T(K) = T(K) + 1;
          break;
        else
          T(K) = 0;
        end
      end
    end

On my system, the maximum that can be constructed is for P = 28, which needs about 6.7 gigabytes.

As far as I know, there are no implementations of the x64 architecture that have more than 48 memory pins. In the case where A is a matrix with only 2 elements, that would give a maximum of P = 42, because 2^43 * 43 entries * 1 byte/entry > 2^48 bytes. However, I wrote the code assuming that you have access to a classified computer with memory capacities exceeding 2*10^9 times as much information stored on Earth as of 2013. (Don't tell me if I am wrong -- I am not authorized to know.)

The code was designed to reduce the memory requirements, not for efficiency.

[yogi yaspranika]

thank's you for answer, sorry I mean the use of not matrices, but for the set if

A^2 = (1,1) (1,2) (2,2) (2,1)

A^3 = (1,1,1)(1,1,2)(1,2,1)(1,2,2)(2,1,1)(2,1,2)(2,2,1)(2,2,2,)

[Walter Roberson]

MATLAB does not have a set data structure. It has array data structures and it has cell array data structures. In my code, each row of AP is one of the members of A^P, where A^P is understood to be ordered P-tuples.

If you were using sets then the only solutions would be:

A^0 = {}   %the empty set
A^1 = {}, {1}, {2}
A^2 = {}, {1}, {2}, {1, 2}

A^(numel(A)+1) and higher are identical to A^(numel(A)) because, for example, {1, 2, 1} as a set is the same as {1, 2} and {2, 1}: by definition sets are unordered and have no duplicates.

Answer 2

[Jan]

How many elements will this set have? Do you want to store 2^100 * 2 elements? A double needs 8 byte and Matlab uses about 100 bytes overhead for each vector. Then you need about:

1267650600228229401496703205376 * (2 * 8 + 100) Byte

147e15 PetaByte. This will let the solar system explode due to the required energy consumption.

So please tell us, which problem you actually want to solve. It is very easy to calculate a specific element and there cannot be any use in storing such a huge array.

[José-Luis]

+1 Come on, it's not even a googolplex.

[John D'Errico]

"how to find A^100 by using Matlab?"

Answer: you don't. You find a better (i.e., doable) way to solve the problem.

Answer 3

[Mahi]

If X and Y are two sets such that n ( X ) = 17, n ( Y ) = 23 and n ( X ∪ Y ) = 38,

find n ( X ∩ Y ).

[Steven Lord]

You shouldn't need to use MATLAB to solve this problem. Draw a picture.