Transcript Chapter 1: Title - Sonoma State University

Lec 14
Oct 22
• more examples of recursive programs
• more about cell arrays
• structures in Matlab
Example showing how insert works
Code for insert
function out = insert(i, lst)
% inserts i into each membet of lst
for j = 1:length(lst)
out{j}= [i, lst{j}];
end;
Code for subsets
function L = subsets(lst)
% generates all subsets of lst
if length(lst) == 0
L = {[]};
elseif length(lst) == 1
L = {[lst(1)],[]};
else
L1 = subsets(lst(2:end));
L2 = insert(lst(1), L1);
L = [L1, L2];
end;
Printing the contents of a cell array
function setprint(cellset)
% prints every member of the cell in one line
% assume cellset is a collection of sets of
integers
for k=1:length(cellset)
aprint(cellset{k}); fprintf('\n');
end;
function aprint(r)
for j = 1:length(r)
fprintf('%d', r(j)); fprintf('
end;
fprintf('\n')
');
Generating all permutations of a given set
Example: set [ 1 3 4]
Permutations:
[1
[1
[3
[3
[4
[4
3
4
1
4
1
3
4]
3]
4]
1]
3]
1]
We will discuss the algorithm and implementation
details in lecture. The problem is part of HW # 4.
More about cell arrays and struct arrays
Cell Arrays
–
–
–
–
Creating Cell Arrays
Accessing Cell Arrays
Using Cell Arrays
Processing Cell Arrays
MATLAB Structures
– Constructing and Accessing One Structure
– Constructor Functions
Structure Arrays
– Constructing Structure Arrays
– Accessing Structure Elements
– Manipulating Structures
Concept: Collecting Dissimilar Objects
Heterogeneous collections permit objects of
different data types to be grouped in a
collection.
– They allow data abstraction to apply to a much
broader range of content.
– However, the fact that the contents of these
collections may be of any data type severely
restricts the operations that can be performed on
the collections as a whole.
– Whereas a significant number of arithmetic and
logical operations can be performed on whole
number arrays, algorithms that process
heterogeneous collections must deal with the data
contents one item at a time.
Cell Arrays
• Cell arrays, as the name suggests, have the
general form of arrays and can be indexed
numerically as arrays.
• However, each element of a cell array should
be considered as a container in which one
data object of any class can be stored.
• They can be treated as arrays of containers
for the purpose of concatenation and slicing.
• However, if you wish to access or modify the
contents of the containers, the cells must be
accessed individually.
Creating Cell Arrays
• By assigning values individually to a variable indexed
with braces:
>> A{1} = 42
A = [42]
• By assigning containers individually to a variable
indexed with brackets:
>> B[1] = {[4 6]};
B = [1x2 double]
• By concatenating cell contents using braces {. . .}:
>> C = {3, [1,2,3], 'abcde'}
C = [3] [1x3 double] 'abcde'
• By concatenating cell containers:
>> D = [A B C {'xyz'}]
D = [42] [1x2 double] [3] [1x3 double] 'abcde' 'xyz'
Accessing Cell Arrays
Continuing the previous examples, we have
the following:
>> E = D(2) % parentheses - a container
E = [4 6]
However, braces are used to access the
contents of the containers as follows:
>> D{2} % braces - the contents
ans = 4 6
If the right-hand side of an assignment
statement results in multiple cell arrays, the
assignment must be to the same number of
variables.
.
Using Cell Arrays
• Containing lists of possible values for
switch/case statements
• Substituting for parameter lists in function calls
– For example, suppose you have a function
largest(a, b, c) that consumes three variables
and produces the largest of the three values
provided. It can be used in the following styles:
A = 4;
B = 6;
C = 5;
N = largest(A, B, C)
params = { 4, 6, 5 };
N = largest(params{1:3})
Processing Cell Arrays
• The template for processing cell arrays is:
<initialize result>
for <index specification>
<extract an element>
<check the element accordingly>
<process the element
accordingly>
end
<finalize result>
Processing Cell Arrays
• Checking the class of the element can be
achieved in one of two ways:
– The function class(item) returns a string specifying
the item type that can be used in a switch
statement
– Individual test functions can be used in an if... elseif
construct;
– examples of the individual test functions are
isa(item, 'class'),
– iscell(...), ischar(...), islogical(...),
isnumeric(...), and
– isstruct(...)
MATLAB Structures
• Structures allow items in the collection to be
indexed by field name.
• The data contained in a structure is
referenced by field name, e.g., item1.
• The rules for making a field name are the
same as those for a variable.
• Fields of a structure, like the elements of a cell
array, are heterogeneous—they can contain
any MATLAB object.
Constructing and Accessing One Structure
• To set the value of items in a structure A, the syntax is
as follows:
>> A.item1 = 'abcde'
A =
item1: 'abcde'
>> A.item2 = 42
A =
item1: 'abcde'
item2: 42
• Fields in a structure are accessed in the same way—
by using the dotted notation.
>> A.item2 = A.item2 ./ 2
A =
item1: 'abcde'
item2: 21
Manipulating Field Names
• To determine the names of the fields in a structure, the
built-in function fieldnames(...) returns a cell array
containing the field names as strings.
>> names = fieldnames(A)
names =
'item1'
'item2’
• Fields can also be accessed “indirectly” by setting a
variable to the name of the field, and then using
parentheses to indicate that the variable contents
should be used as the field name:
>> fn = names{1};
>> A.(fn) = [A.(fn) 'fg']
A =
item1: 'abcdefg'
item2: 21
More about Field Names
• You can remove a field from a structure using
the built-in function rmfield(...).
• Be careful. rmfield(...) returns a new structure
with the requested field removed. It does not
remove that field from your original structure.
• If you want the field removed from the original,
you must assign the result from rmfield(...) to
replace the original structure:
>> A = rmfield(A, 'item1')
A =
item2: 21
Why Constructor Functions?
Use constructor functions, as opposed to
“manually” entering data into structures, for the
following reasons:
– Manual entry can result in strange behavior due
to typographical errors or having fields in the
wrong order
– The resulting code is generally more compact and
easier to understand
– When constructing collections of structures, it
enforces consistency across the collections
Built-in Constructor Function struct(…)
>> struct('first','Fred', ...
'last','Jones', ...
'phone','(123) 555-1212', ...
'birth', struct( 'day', 31, ...
'month', 'February', ...
'year', 1965 ))
ans =
first: 'Fred'
last: 'Jones'
phone: '(123) 555-1212'
birth: [1x1 struct]
Custom Constructor Functions
• A typical custom constructor function
function ans = makeCD(gn, ar, ti, yr, st, pr)
% integrate CD data into a structure
ans.genre = gn ;
ans.artist = ar ;
ans.title = ti;
ans.year = yr;
ans.stars = st;
ans.price = pr;
• Usage:
>> CD = makeCD('Blues', 'Charles, Ray’,
'Genius Loves Company', 2004, 4.5, 15.35 )
CD =
genre: 'Blues'
artist: 'Charles, Ray'
title: 'Genius Loves Company'
year: 2004
stars: 4.5000
price: 15.3500
Building Structure Arrays Manually
>> entry(1).first = 'Fred';
>> entry(1).last = 'Jones';
>> entry(1).age = 37;
>> entry(1).phone = ' (123) 555-1212';
>> entry(2).first = 'Sally’;
>> entry(2).last = 'Smith’;
>> entry(2).age = 29;
>> entry(2).phone = '(000) 555-1212'
entry =
1x2 structure array with fields:
first
last
age
phone
Building Structure Arrays with struct(…)
genres = {'Blues', 'Classical', 'Country' };
artists = {'Clapton, Eric', 'Bocelli, Andrea', …
'Twain, Shania' };
years = { 2004, 2004, 2004 };
stars = { 2, 4.6, 3.9 };
prices = { 18.95, 14.89, 13.49 };
cds = struct( ‘genre’, genres, …
'artist', artists, …
'year', years, …
'stars', stars, …
'price', prices);
Building Structure Arrays with makeCD(…)
cds(1) = makeCD('Blues', 'Clapton, Eric', ...
'Sessions For Robert J', 2004, 2, 18.95 )
cds(2) = makeCD('Classical', ...
'Bocelli, Andrea', 'Andrea', 2004, 4.6, 14.89 )
cds(3) = makeCD( 'Country', 'Twain, Shania', ...
'Greatest Hits', 2004, 3.9, 13.49 )
cds(4) = makeCD( 'Latin', 'Trevi, Gloria', ...
'Como Nace El Universo', 2004, 5, 12.15 )
cds(5) = makeCD( 'Rock/Pop', 'Ludacris', ...
'The Red Light District', 2004, 4, 13.49 )
cds(6) = makeCD( 'R & B', '2Pac', ...
'Loyal To The Game', 2004, 3.9, 13.49 )
cds(7) = makeCD( 'Rap', 'Eminem', ...
'Encore', 2004, 3.5, 15.75 )
cds(8) = makeCD( 'Heavy Metal', 'Rammstein', ...
'Reise, Reise', 2004, 4.2, 12.65 )
Summary
■ Cell arrays are vectors of containers; their
elements can be manipulated either as vectors
of containers, or individually by inserting or
extracting the contents of the container using
braces in place of parentheses.
■ The elements of a structure are accessed by
name rather than by indexing, using the dot
operator to specify the field name to be used.
■ Structures can be collected into structure
arrays whose elements are structures all with the
same field names. These elements can then be
indexed and manipulated in the same manner
as the cells in a cell array.
Recursive backtracking – project
The next problem introduces a general technique of
problem solving that can be used in a wide range of
settings. We will use it to solve the following problem: a
Latin square of order n is a n by n square matrix in which
each row and each column contains exactly one
occurrence of numbers 1 to n. (In mid-term, you wrote a
program to test if a given matrix is a Latin square.)
Our problem is more complicated – given a partially
filled Latin square, we want to complete it into a Latin
square, if possible.