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