perm filename PERLMN.LET[DOC,LMM] blob
sn#044089 filedate 1973-05-18 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 $$
C00008 ENDMK
C⊗;
$$;
David M. Perlman
University of California, San Diego
La Jolla, California 92037
Dear David:
$JI read with interest the paper you sent me. Your algorithm
parallels very closely some parts of the algorithm published in the
paper which I am sending you. I must say that the description in
the paper is not the clearest. The problem attacked is slightly
more general: one wishes to find a system of distinct
representatives for a tuple of subsets of X, where G acts on X, and
each tuple is of the form (U↓1,U↓2,...,U↓k) where the U↓i's are
disjoint, and |U↓i|=n↓i. We call this "labelling" X such that n↓i of
the elements of X recieve label i. In the special case where k=2,
this corresponds directly to finding an s.d.r. of n↓1-subsets of X.
However, the first result is that one can label with k types of
labels by labelling with the first type of label, and then labelling
the "unlabelled" elements of X with the remaining labels, using the
reduced symmetry group. The next result is that if G is not
transitive (i.e., if there are orbits of G as it acts on X), then
one can do one orbit at a time.
Thus the problem reduces to something similar to the one in your
paper (it is also know that the group is transitive). The third
result is very similar to yours; one constructs a set which
contains an s.d.r. but might actually have equivalent items;
those are eliminated by checking each of the results if they
are "minimal" according to a lexicographical ordering. The
"candidate" sets, however, are different; I believe, now,
that there is a whole class of possible candidate sets one
could chose in order to find a s.d.r; for example, I chose,
at the time:
To find an s.d.r. for k-subsets of X under the group G,
find an s.d.r. of (k-1)-subsets of X-{x↓1} under the stabilizer
subgroup of {x↓1}; the set of candidates is then the set of
those results, conjoined with {x↓1}. In general, one could
choose to take an s.d.r. of i-subsets of X, and then for each U in that s.d.r.,
find an s.d.r. of (k-i)-subsets of (X-U) wrt the stabilizer of U.
In your case, you took i=k-1; in mine, I chose i=1 (since G is
transitive, {{x↓1}} is an s.d.r. of 1-subsets of X under G).
I am not sure, off hand, which i is optimal; you're solution
has merit. It might be interesting to do some analysis of the
efficiency of these algorithms; any such constructive algorithm
must take at least as many number of steps as there are possible
solutions; further, it seems difficult to find an algorithm
which would take less than |G|*|s.d.r.|. I wonder how close
any of these methods might come to that bound.
As for your paper, I only have a few comments:
There is some confusion between "enumerating" and "counting", despite
Le Berge's clarification; I would suggest emphasis that you have
a method for construction, and not just counting.
Also, I am not sure how appropriate the word "backtracking" is; I have
a prejudice that "backtracking" applies to search procedures, rather
than generative procedures; admitedly, generative procedures have
very little use outside of providing candidates for additional
heuristics in a search application.
But this is all just quibbling with wording. I thank you for sending
me your paper and hope we can correspond in the future.
Sincerely,
Larry Masinter