[Edu-sig] More permutation madness [Cryptonomicon]

[Daniel Yoo]

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.
  Send mail to mime@docserver.cac.washington.edu for more info.

--545289610-2108799327-975584035=:15623
Content-Type: TEXT/PLAIN; charset=US-ASCII


There was a question about ways of generating permutations: is there an
easy way to show that these two functions:

###
def permuteRestricted(L):
    newlist = L[:]   # shallow copy
    for i in range(len(L)):
        rand_i = randint(i, len(L)-1)
        newlist[i], newlist[rand_i] = newlist[rand_i], newlist[i]
    return newlist

def permuteUnrestricted(L):
    newlist = L[:]   # shallow copy            
    for i in range(len(L)):                   
        rand_i = randint(0, len(L)-1)
        rand_j = randint(0, len(L)-1)
        newlist[rand_j], newlist[rand_i] = newlist[rand_i],
newlist[rand_j]
    return newlist
###

act differently?

I tried to prove this difference by brute force: the attached program
generates the whole space of permutations, given these two methods.  I
have to apologize for the code's uglyness and sluggishness, and if anyone
can simplify or optimize it, I'd be very happy.

I hope this helps!

--545289610-2108799327-975584035=:15623
Content-Type: TEXT/PLAIN; charset=US-ASCII; name="countPerms.py"
Content-Transfer-Encoding: BASE64
Content-ID: <Pine.LNX.4.21.0011300333550.15623@hkn.eecs.berkeley.edu>
Content-Description: 
Content-Disposition: attachment; filename="countPerms.py"

IiIiVGhpcyBpcyBhIHNtYWxsIHNjcmlwdCB0aGF0IHNob3dzIHRoZSBkaWZm
ZXJlbmNlIGJldHdlZW4gdHdvDQpzaHVmZmxpbmcgbWV0aG9kcy4gIEl0IHNo
b3VsZCBzaG93IHRoYXQgb25lIGFwcHJvYWNoIGRvZXNuJ3QgZXZlbmx5DQpn
ZW5lcmF0ZSBjZXJ0YWluIHR5cGVzIG9mIHNodWZmbGluZy4NCg0KRG8gdGhl
IGZvbGxvd2luZyBmdW5jdGlvbnM6DQoNCiMjIw0KZGVmIHBlcm11dGVSZXN0
cmljdGVkKEwpOg0KICAgIG5ld2xpc3QgPSBMWzpdICAgIyBzaGFsbG93IGNv
cHkNCiAgICBmb3IgaSBpbiByYW5nZShsZW4oTCkpOg0KICAgICAgICByYW5k
X2kgPSByYW5kaW50KGksIGxlbihMKS0xKQ0KICAgICAgICBuZXdsaXN0W2ld
LCBuZXdsaXN0W3JhbmRfaV0gPSBuZXdsaXN0W3JhbmRfaV0sIG5ld2xpc3Rb
aV0NCiAgICByZXR1cm4gbmV3bGlzdA0KIyMjDQoNCmFuZA0KDQojIyMNCmRl
ZiBwZXJtdXRlVW5yZXN0cmljdGVkKEwpOg0KICAgIG5ld2xpc3QgPSBMWzpd
ICAgIyBzaGFsbG93IGNvcHkgICAgICAgICAgICANCiAgICBmb3IgaSBpbiBy
YW5nZShsZW4oTCkpOiAgICAgICAgICAgICAgICAgICANCiAgICAgICAgcmFu
ZF9pID0gcmFuZGludCgwLCBsZW4oTCktMSkNCiAgICAgICAgcmFuZF9qID0g
cmFuZGludCgwLCBsZW4oTCktMSkNCiAgICAgICAgbmV3bGlzdFtyYW5kX2pd
LCBuZXdsaXN0W3JhbmRfaV0gPSBuZXdsaXN0W3JhbmRfaV0sIG5ld2xpc3Rb
cmFuZF9qXQ0KICAgIHJldHVybiBuZXdsaXN0DQojIyMNCg0KZG8gdGhlIHNh
bWUgdGhpbmc/DQoNClRoZSBmb2xsb3dpbmcgcHJvZ3JhbSB0cmllcyB0byBz
aG93IHRoYXQgdGhlcmUgSVMgYSBkaWZmZXJlbmNlIGJldHdlZW4NCnRoZW06
IHRoZXkgcHJvZHVjZXMgZGlmZmVyZW50IGRpc3RyaWJ1dGlvbnMgb2YgcGVy
bXV0YXRpb25zLCB0aGF0IGlzLA0KdW5kZXIgdW5kcmVzdHJpY3RlZCByYW5k
b20gc3dhcHBpbmcsIGNlcnRhaW4gcGVybXV0YXRpb25zIGFyZSBtb3JlDQpj
b21tb24gdGhhbiBvdGhlcnMhDQoNCldlIGRvIHRoaXMgYnkgY29uc3RydWN0
aW5nIHRoZSB3aG9sZSBzcGFjZSBvZiBwZXJtdXRhdGlvbnMgYWNjb3JkaW5n
DQp0byBlYWNoIG1ldGhvZC4gIEFmdGVyIGNvbnN0cnVjdGlvbiwgd2UgY291
bnQgdGhlIGRpc3RyaWJ1dGlvbnMuIiIiDQoNCg0KZnJvbSBvcGVyYXRvciBp
bXBvcnQgYWRkDQpkZWYgbWFwcGVuZChmLCBMKToNCiAgICAiIiJBcHBseSBh
IGZ1bmN0aW9uIG9uIGVhY2ggZWxlbWVudCBvZiB0aGUgbGlzdCwgYW5kIGFw
cGVuZCBhbGwNCiAgICBpdHMgcmVzdWx0cy4gIFVzZWZ1bCB3aGVuIGYoeCkg
aXRzZWxmIHJldHVybnMgYSBsaXN0IG9mIHZhbHVlcyBmb3INCiAgICBlYWNo
IHggaW4gTC4gICIiIg0KICAgIHJldHVybiByZWR1Y2UoYWRkLCBtYXAoZiwg
TCkpDQoNCmRlZiBkaXN0SGFzaChMKToNCiAgICAiIiJSZXR1cm4gYSBoYXNo
IG9mIHRoZSBkaXN0cmlidXRpb24gb2YgdGhlIGVsZW1lbnRzLiAgRWFjaA0K
ICAgIGVsZW1lbnQgbXVzdCBiZSBhbiBpbW11dGFibGUgdGltZTsgb3RoZXJ3
aXNlIHdlIGNhbid0IHVzZSBpdCBhcyBhDQogICAgaGFzaCBrZXkuIiIiDQog
ICAgcmVzdWx0ID0ge30NCiAgICBmb3IgeCBpbiBMOg0KICAgICAgICByZXN1
bHRbeF0gPSByZXN1bHQuZ2V0KHgsIDApICsgMQ0KICAgIHJldHVybiByZXN1
bHQNCg0KZGVmIGdldFN3YXBwZWRQZXJtKHBlcm0sIGksIGopOg0KICAgICIi
IlJldHVybiB0aGUgcmVzdWx0aW5nIHBlcm11YXRpb24gYWZ0ZXIgb25lIHN3
YXAgYmV0d2VlbiBwZXJtW2ldDQogICAgYW5kIHBlcm1bal0iIiINCiAgICBy
ZXN1bHQgPSBwZXJtWzpdDQogICAgcmVzdWx0W2ldLCByZXN1bHRbal0gPSBy
ZXN1bHRbal0sIHJlc3VsdFtpXQ0KICAgIHJldHVybiByZXN1bHQNCg0KZGVm
IGdlbmVyYXRlVW5yZXN0cmljdGVkKHBlcm0sIGkpOg0KICAgICIiIlJldHVy
biBhbiB1bnJlc3RyaWN0ZWQgZXhwYW5zaW9uIG9mIHBlcm11dGF0aW9ucywg
Z2l2ZW4gYSBiYXNlDQogICAgcGVybXV0YXRpb24gInBlcm0iLg0KDQogICAg
VGhpcyBpbnRlbnNpb25hbGx5IGlnbm9yZXMgdGhlIGJvdW5kYXJ5IGkuDQog
ICAgIiIiDQogICAgcmVzdWx0cyA9IFtdDQogICAgZm9yIGogaW4gcmFuZ2Uo
bGVuKHBlcm0pKToNCiAgICAgICAgZm9yIGsgaW4gcmFuZ2UobGVuKHBlcm0p
KToNCiAgICAgICAgICAgIHJlc3VsdHMuYXBwZW5kKGdldFN3YXBwZWRQZXJt
KHBlcm0sIGosIGspKQ0KICAgIHJldHVybiByZXN1bHRzDQoNCmRlZiBnZW5l
cmF0ZVJlc3RyaWN0ZWQocGVybSwgaSk6DQogICAgIiIiUmV0dXJuIHRoZSBl
eHBhbnNpb24gb2YgcGVybXV0YXRpb25zLCBnaXZlbiBhIGJhc2UgcGVybXV0
YXRpb24NCiAgICAicGVybSIuDQoNCiAgICBUaGUgcGFyYW1ldGVyICdpJyBy
ZXN0cmljdHMgd2hhdCBraW5kcyBvZiBwZXJtdXRhdGlvbnMgYXJlDQogICAg
YXZhaWxhYmxlIHRvIGdlbmVyYXRlLiIiIg0KICAgIA0KICAgIHJlc3VsdHMg
PSBbXQ0KICAgIGZvciBqIGluIHJhbmdlKGksIGxlbihwZXJtKSk6DQogICAg
ICAgIHJlc3VsdHMuYXBwZW5kKGdldFN3YXBwZWRQZXJtKHBlcm0sIGksIGop
KQ0KICAgIHJldHVybiByZXN1bHRzDQoNCmRlZiBnZXRQZXJtdXRhdGlvbnMo
biwgZnVuYyk6DQogICAgIiIiR2VuZXJhdGUgdGhlIHdob2xlIHNwYWNlIG9m
IHBlcm11dGF0aW9ucywgZ2l2ZW4gYSBwZXJtdXRpbmcNCiAgICBmdW5jdGlv
biAiZnVuYy4iDQogICAgIiIiDQogICAgcGVybVNwYWNlID0gWyBsaXN0KHJh
bmdlKG4pKSBdICAjIG91ciBpbml0aWFsIHNwYWNlIGNvbnRhaW5zDQogICAg
ICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgdGhlIGlkZW50aXR5IHBl
cm11dGF0aW9uLg0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAj
IFdlIHdpbGwgZXhwYW5kIHRoaXMuDQogICAgZm9yIGkgaW4gcmFuZ2Uobik6
DQogICAgICAgIHBlcm1TcGFjZSA9IG1hcHBlbmQobGFtYmRhIHAsIGk9aSwg
ZnVuYz1mdW5jOiBmdW5jKHAsaSksIHBlcm1TcGFjZSkNCiAgICByZXR1cm4g
cGVybVNwYWNlDQoNCg0KZGVmIF9tYWluKG4pOg0KICAgIHJpZ2h0ID0gZ2V0
UGVybXV0YXRpb25zKG4sIGdlbmVyYXRlUmVzdHJpY3RlZCkgICAgICMgbG9h
ZGVkIHdvcmRzLi4uDQogICAgcHJpbnQgIlJlc3RyaWN0ZWQgc3dhcHBpbmc6
IiAsIGRpc3RIYXNoKG1hcCh0dXBsZSwgcmlnaHQpKQ0KICAgIA0KICAgIHdy
b25nID0gZ2V0UGVybXV0YXRpb25zKG4sIGdlbmVyYXRlVW5yZXN0cmljdGVk
KQ0KICAgIHByaW50ICJVbnJlc3RyaWN0ZWQgc3dhcHBpbmc6IiwgZGlzdEhh
c2gobWFwKHR1cGxlLCB3cm9uZykpDQoNCiMgRHJpdmVyIGZ1bmN0aW9uLiAg
QW55dGhpbmcgbW9yZSB0aGFuIDMgd2lsbCBjYXVzZSBhIExPVCBvZiB3b3Jr
Lg0KaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoNCiAgICBwcmludCAiSGVy
ZSdzIGEgc3VtbWFyeSBvZiBwZXJtdXRhdGlvbnMgbGVuZ3RoIDM6Ig0KICAg
IF9tYWluKDMpDQogICAgcHJpbnQNCiAgICBwcmludCAiSGVyZSdzIGEgc3Vt
bWFyeSBvZiBwZXJtdXRhdGlvbnMgbGVuZ3RoIDQ6Ig0KICAgIF9tYWluKDQp
DQoNCg0K
--545289610-2108799327-975584035=:15623--